操作を好きな回数だけ行える
Codeforces
最適化テク:解を変形していく(最適性を失わずに)
DP
O(3^N)
bitDP
Greedy
前処理
行列
最適化テク:探索候補を絞る
グラフの辺数を削減する
操作
操作:circular_shift
操作後の結果の最適化問題
CodeforcesCombined
CodeforcesR2400
指数探索系問題
マルチテストケース問題
最大スコア
操作を好きな回数だけ行える
最適化問題
すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…
AtCoder
AtCoder600点
ABC-F
Union-Find
連結成分
二部グラフ
二次元平面上のN点の問題
グラフ
可視化テク:二次元情報を二部グラフにして考える
制約条件:長方形の4頂点についての条件
青色diff
連結成分ごとに分解して考える
操作
操作後の結果の最適化問題
操作を好きな回数だけ行える
操作:辺を追加する
なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…
AtCoder
AtCoder400点
AGC-B
操作
条件の言い換え
操作:上書き
操作を逆順に見る
操作:区間
区間
必要条件を列挙したら十分条件になる
累積和
数列
前処理
操作後の結果の最適化問題
最大スコア
青色diff
負値が本質的に効く問題
操作を好きな回数だけ行える
0と1の問題
累積和テク:累積和や累積結果を前処理しておく
最適化問題
操作を逆順に見るとよいという、すごく良い例題！大好き！！！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…
