- 追加された行はこの色です。
- 削除された行はこの色です。
[[プロコン]]
*まとめと例題 [#sb6823fa]
|方針|説明|例題|h
|DPテーブルを書いてみて、混み合っている場合は無駄な計算がないか考える||2-3 漸化式を工夫する, 個数制限なしナップザック問題|
|boolのDPは一般に非効率||2-3 漸化式を工夫する, 個数制限付き部分和問題|
|DPの双対性|「状態に対して評価値がどうなるか」⇔「固定された評価値（＝ここでの状態）に対して、最も良い状態（＝ここでの評価値）は何か」|(2-3 漸化式を工夫する, 01ナップサック問題その2, 最長部分増加部分列問題）|
|「fの最大化」⇔「命題C(x)=『fがx以上である』が判定可能ならば、xの探索的最大化」||3-2 平均最大化|
|n回の掛け算はO(log n)で計算可能||3-1 べき乗を高速に計算する|
|漸化式は行列演算に変換可能||3-5 行列累乗|
|modはどこでしても同じ||3-5 行列累乗, SRM 502 Div2 Hard|
|集合を、整数型のビット演算を用いてDPの状態に組み込む||3-5 ビットDP|
|DPは適切なデータ構造を用いると高速化||3-5 データ構造を用いて高速化|
|問題を同値な数学に置き換える|牛が云々とかいう状態で考えたくない|SRM 502 Div2 Hard|
|DPのデータ型のパターンはいっぱいある|6次元配列だろうが何だろうがビビらない|SRM 551 Div2 Hard, [[桁DP>http://pekempey.hatenablog.com/entry/2015/12/09/000603]]|
|一つ前にしか依存しないDPテーブルは2テーブルを使いまわす|int prev=i%2,next=prev^1; memset(dp[next], 0, sizeof(dp[next])); dpdp[next][(x+i)%N][y-1] += dpdp[prev][x][y];.絶対，dp[next]を初期化すること！！最後のテーブルの添字は毎回きちんと考えなければならない．|SRM 502 Div2 Hard|
|最小手数といえば幅優先探索||SRM 509 Div2 Hard|
|A以上B以下のもの|f(n):=n以下の条件を満たす非負整数の総数とすればf(B)-f(A-1)|[[桁DP>http://pekempey.hatenablog.com/entry/2015/12/09/000603]]|
|n進数の不定長データ列の生成はqueueを使う(A, B, C, AA, AB, ...など)|[[サンプルコード>https://github.com/hamko/sample/blob/master/c%2B%2B/algorithm/pow_n_m.cpp]]|SRM 682 Div2 Medium|
|マジックナンバーは消す|バグの温床になる||
|負のDP|const int MAX = 1000; int ary[2*MAX + 1]; int *dp = ary + MAX; // [-MAX, MAX]にアクセスできる!||
|二段DP||SRM 523 Div2 Hard|
|DPは問題の制約を気にせず解いて，後でまとめるときに制約を考える|円卓テーブルで隣り合って同じ色はダメ→同じ色も許容するDPを組んで，後で違う色の場合の数だけ集める|SRM 551 Div2 Hard|
|単調増加DPは変化分だけを追うDPに変換する||[[Yukicoder 269>http://kmjp.hatenablog.jp/entry/2015/08/22/0930]]|
|包除原理|全体からある条件f1, f2, f3...を除いた場合の数＝S(全\(f1orf2orf3orf4)) = S(全) - S(f1) - S(f2) - S(f3) - S(f4) S(f1&&f2) + S(f1&&f3) + ... - S(f1&&f2&&f3) - S(f1&&f2&&f4) ... + S(f1&&f2&&f3&&f4)。2^条件数で求まる|ABC 3D|
|二次元の累積和は、前処理O(n)でO(1)になる|「0からiのx方向累積和の参照」をの累積和y方向に取ればよい。|ABC 5D|
|「n個ちょうど使ったら」という発想大事||ABC 5D|
|配るDP＆空間を削減するDPの場合、iごとに初期化を忘れない！！|すごく忘れやすい。空間を使いまわしてるので初期化必須。|ABC 7D|
|バイナリ状態を表すDPは、「j: ○○が確定している」という表現をする|なぜなら、j bitor (○○)と表現して遷移が書けるから|ABC 7D|
|桁のDPは上から見ていく||ABC 7D|
|漸化式の計算は行列累乗と相性がいい||ABC 9D|
|行列演算は半環なら可能|要するに掛け算と足し算（*+, AND-OR, AND-XOR）が定義可能|ABC 9D|
|容量1の最大流問題は、同じ道を通らない最大経路数に一致||ABC 10D|
|最大流最小カット定理|容量1の最大流は、最小カットに一致。|ABC 10D|
|容量1の最大流問題は、Ford Fulkersonが速い||ABC 10D|
|modと-とif文の相性は最悪|何気なく、if (n % 2 == x % 2) continue; とか書くと死 (x負で死)。何気なく、if ((n - m) % 2 == 1) continue; とか書くと死 (n < mで死)|ABC 11D|
|100万要素を超えるテーブル・10万頂点を超えるグラフはグローバルに置くかstaticをつける|スタック領域には入らない可能性|ABC 14D|
|DPを回す添字の上下には注意、+1になったりする。|注意するしかない。あるいは、repを使っているのがいけないのか。|ABC 15D|
|dpが0であることと、配れないことは同値ではない|始め0でも、あとで+bして配ったりするので。|ABC 15D|
|DPのデバッグは、iの下で別のループを使って0以外を出力。|遷移のループの中ではなく、下に新しいループを作る！また、自明なdpの項は出さない。rep(j, k + 1) rep(h, w + 1) { if (dp[next][j][h]) cout << i << " : " << j << " " << h << " : " << dp[next][j][h] << endl; }|ABC 15C|
|一周回るときの漸化式はa[i] - a[(i+1)%n]とmodを使うときれい||ABC 16D|
|mod系は、-が含んでいると、答えが-になりえる||ABC 17D|
|半分全列挙強い|片方が固定されていると、もう片方が楽に取れることがある。マージ則が軽ければいける。今回のように男女に分かれている時もあれば、ナップザックの時みたいに自分で分けることも|ABC 18D|
|木の直径はO(V)で計算可能で、二回走査すればよい。||ABC 19D|
|二分探索の初期値は、upperは必ず条件を満たすもの、lowerは必ず条件を満たさないものを選ぶ。|更新はwhile (r - l != 1) { ll mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; }|ABC 23D|
|整数a, b、素数p、a/bが整数の時、a/b (mod p) = a * b ^ (p-2) (mod p)||ABC 24D|
|「配るDP」と「集めるDP」がある。|漸化式の可換性があれば「配れる」。(+), (*), min, maxなどは配れる|ABC 25D|
|配るDPは、 iで配ったものが必ずその後にしか影響しないならば、順方向に見ていけばOK|トポロジカルソートでも同じことが言える。|ABC 25D|
|配るDPの場合には、0を配ろうとして無駄なので、さっさとcontinueする。|高速化のため。集めるDPはそもそもいらないものは見ないので良いが、配るのはそうはいかない。|ABC 25D|
|順序がついているとn!の探索空間になるが、順序をなくすと2^nに落ちる。||ABC 25D|
|bit集合では常に、集合S<集合Sに何か埋めた集合||ABC 25D|
|bit集合の参照は楽なので、ラッパ関数とか作らないほうがわかりやすい||ABC 25D|
|DPのループの順番は、依存関係の強いものを左に、弱いものを右に持ってくる。||ABC 25D|
|setは、insert, erase, countをよく使う。||ABC 25D|
|左右のどちらかだけ埋まっている、という条件は、^演算子を使うとやりやすい。||ABC 25D|
|誤差系は、型long double, 二分探索40000回、表示40桁あれば絶対安全。|long long doubleのサイズによる|ABC 26D|
|long doubleの表示は%Lf, doubleは%lf, floatは%f（物議はあるが）||ABC 26D|
|制約なし（今回は戻ってきて原点）を前提として、問題が解けるかを考えるのは大事|そもそもDPもそういう発想だし|ABC 27D|
|A->Bの効果が累積する系は、逆にB->Aの効果の累積となる|数学的構造はどうなってる？？|ABC 27D。ARC 41C|
|左しか影響しない、などの依存性の考察大事||ABC 27D|
|紙できちんとできることを確認してからやること！！漸化式いじりすぎ。||ABC 29D|
|間違ってないなら、枝刈り条件を削らない|残して間違えたとするなら、枝刈り能力が足りないのだ|ABC 29D|
|1indexは絶対0indexに！頭がこんがらがってしょうがない。||ABC 30D|
|3進数の全探索|rep(i, pow(3, K)) { vector<int> len(K); int tmp = i; rep(j, K) len[j] = tmp % 3, tmp /= 3;}|ABC 31D|
|ごちゃごちゃしてる時は大きい紙で整理するのと、遠慮なく変数を大量に作る。iとかjとかだとよくわからなくなる。||ABC 31D|
|デバッグ用の添字は_をつけるとかしたほうがいい。もしくは、そもそもデバッグ用のマクロを作るという手もある。||ABC 31D|
|stack, queueでは、探索の辺前後の状態変化可逆性を利用した空間計算量削減ができない||ABC 31D|
|単射な構造は、入出力を逆にした双対問題みたいのものを考えられる。|重さ→価値は単射なので、以下の二つの問題はだいたい同じ。「重量jをぴったり使用する時、最大達成価値f」「価値j*をぴったり達成する時、最小使用重量f」|ABC 32D|
|INFはconst long long INF = 1e18;などとするのがいい。||ABC 32D|
|lower_boundはval以上の最小の値を指すイテレータ、upper_boundはより大きい最小の値を指すイテレータ。||ABC 32D|
|以下、より小さいの条件で二分探索する場合は、そもそもsortを降順で行っておく||ABC 32D|
|push_backするfor文の条件は、静的なサイズを指定。||ABC 33D|
|EPSは1e-14||ABC 33D|
|atan2は(y, x)||ABC 33D|
|complexはデフォルト提供されてる唯一のベクトル||ABC 33D|
|演算子はキャスト * + =の順番で、順番をきちんと意識しないと型間違えて死ぬ。|double a = 1.0 * a + 2 * a * f; は死|ABC 33D|
|予めどれくらいpush_backするかわかってる場合はreserveすべき。||ABC 33D|
|pairは辞書順ソート||ABC 33D|
|Complexはreal, imagのどちらかだけを再設定する、ということはできない||ABC 33D|
|実験大事||ARC 51C|
|逆元はmodが素数じゃなかったら即刻諦めること！|頑張っても無駄|ARC 51C|
|if (np & 1 == 0)はダメ。bitは()でくくること。||ARC 49C|
|XORの逆演算はXOR！||ARC 45C|
|最小云々はなんと言うかギザギザしてる構造を持っている気がするので、愚直にできなければDPか二分探索を考えるべき||ARC 44C|
|x, yとある場合、独立性を判断する。別々に解いていいことがある。||ARC 44C|
|ノードに付帯情報をつけるといいことがある|例えば、(i, j)の隣のマスは(i, j-h)であるみたいな|ARC 39C|
|素数はだいたい1000万まで、だいたい1/10個くらい。（1000万で6.6%）||ARC 34C|
|最短閉路問題は簡単|(O(V^3): ワーシャルフロイドO(V^3+全点走査O(V)*2点選びO(V^2))閉路に含まれる1点Pを削除することを考え、点Pと辺でつながっていた頂点の中から2点QRを選び、QRの最短経路コスト+辺PQコスト+辺PRコスト、で済む。|ABC ???|
|Mod構造体の^も()つけまくる|優先順位||
|嘘解法：大きいllの掛け算が面倒になったら、ldを介してしまう。|ceill(((ld)t * (ld)x - (ld)r) / ((ld)x - (ld)1) - (ld)1e-14)||
|整数の割り算には注意|符号によってガウス記号の上下が変わるから。ちゃんとlgauss, ugaussを使いましょう|ARC 8B|
|Mod構造体は最小限に|勝手にmodされては困るケースがある||
|〜してはならない、みたいな条件は面倒なので、だめなのはわかってながらも全部足してから、後で引けないか考える。|包除原理もそういうふうになっているはず|ABC17C|
|紙に書いて考察せよ||ABC23C|
|a+b=nなる非負整数を求めるとき、ループの範囲に注意||ABC23C|
|cout << 1 << endl; return 0;を徹底。|atcoder, codeforcesでは||
|漸化式の依存方向と、ループの方向は「自然」に一致させる|自然とは、「後にのみ依存するならi=0->n」「前にのみ依存するならi=n->0」。そうすると、メモリが使いまわせる。一方向にのみ依存するDPなどが使えるし、異常条件も減る||
|逆演算の存在は主に0-indexをi-indexにできる|||
|走査系ははじめに安心安全なprevで初期化しておくと、境界条件が減ってバグが減る||ARC 16B|
|以下、より小さいのlower_boundは、sortも''lower_boundも''comp入れないとだめ。||ARC 37C|
|for all, there existのcontinueはgoto文を使うべき|とても簡潔になっていい|ABC 02D|
|有向グラフの閉路列挙は強連結成分分解する||ARC 49C|
|前k個のみに依存するDP|kが小さくk個のパターンが列挙できるか？もしできるなら全部覚えてしまえばいい。もし全部覚えられそうにないなら特徴抽出する|ARC 36C|
|mapはunordered_mapの3倍遅い|||
|mapはfindメンバ関数をサポート|返り値はnot foundでm.end()|ARC 17C|
|同じ処理を二度やるときにラムダを使うと見通しがいい||ARC17C|
|関数fが定義域全体で既知なら、f^nはO(log n)で計算可能|何回もちまちま同じことやってるなーと思ったら、ダブリングを検討|ABC 13D|
|同心円の存在するベン図は、同心円ごとにまとめてvectorやmapなどで表現する||ABC 20D|
|mapをキーにしたmapが可能||ABC 20D|
|mapのメモ化条件では必ずcount関数を使う||ABC 20D|
|不定次元数かつ凸凹な多重ループは、intで0からΠa[i].size()のループを作る|ループ内でint tmpi = i; tmpi %a[i].size(), tmpi/=a[i].size();で添字を取得可能（3^nの全探索++みたいな感じ）|ABC 20D|
|メモ化探索で、初期条件はメモに突っ込んでおけばいい||ABC 20D|
|平均の最大化は二分探索が有効||ABC 34D|
|unordered_mapはハッシュなので、意地悪されうる|時間がありそうならmapを使う。何もしないケースで落とされないように、reserveでhackを難しくする|Codeforces 350C|
|Codeforcesのサーバの速度は、ノートパソコンの10倍はやい||Codeforces 350C|
|Codeforcesのハックはカスタムテストを使わないとだめ||Codeforces 350C|
|二分探索の最大値は大きいので、check関数内部でオーバーフローしないか、最大ケースで事前にチェック||Codeforces 350D|
|nサイクルの置換fは、f^nを計算するとサイクルが分割する||SRM 546 D1H|
|十進数の問題は、桁ごとに見ていく||SRM 546 D1M|
|数値リテラルはきちんと型を指定する|1 << nは、n > 32で死ぬ。1ll << nとすること。1.0はdouble, 1はint, 1.0lはlong double, 1llはlong long, 1e10はdouble|SRM 546 D1E|
|*2とか+1とかは、二進数で考えたほうが楽。何進数で考えるべきなのかを考える||SRM 546 D1E|
|大きい配列はglobalかstaticに持つ||ATC01 C|
|入出力が遅いので、Clangで提出してはいけない||Atcoder 52D|
|括弧列が正常ならば、対応する括弧は(で+1, )で-1を繰り返して0になるところとして計算できる。|O(n)|Codeforces 351 D2C|
|シミュレーション問題は、ちゃんと手でシミュレーションしないとミスりまくる||Codeforces 351 D2C|
|一つ前に進む一つ後ろに進む、という操作は、ランダムアクセスのできないlistと相性がいい||Codeforces 351 D2C|
|一行の出力は、最初を特別扱いするべき|出力しないコンテナがあったりするとこっちのほうがいい|ARC11B|
|盤面反射は盤面外でdi, dj*=-1||ABC05B|
|stringにもiteratorがあるので、begin, endが使える||ABC03B|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
