プロコン/勉強したこと の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• プロコン/勉強したこと へ行く。
• プロコン/勉強したこと の差分を削除

[[プロコン]]


*まとめと例題 [#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|
|整数同士の掛け算があるかはきちんとチェックする||Codeforces 352 D2D|
|任意の整数はフィボナッチ数列で表せる||SRM 687 D1E|
|高度合成数のググり方||SRM 547 D1M|
|「点群x_i(n個)との距離が最小な数l」は、中央値で計算可能||SRM 646 D1E |
|ある非減少の数列を階段状に変化させるときには、変化数が最小になるものは複数ある可能性がありますが、そのうち少なくとも1つは変化させなくて良い数を含みます。|||
|最大連続長の実装は、prevがいらない||ARC10B|
|ゲームの時、障害物に勝利条件を置ける||ARC 38B|
|「〜で絶対に勝てるなら1, 勝てないなら0」という再帰が組める||ARC 38B|
|goto文のラベルの間に変数を定義してはいけない||686 D1E|
|多次元配列の初期化 int a[3][3];　fill(a[0], a[3], 500);|||
|多次元配列の初期化 int b[3][3][3]; fill(b[0][0], b[3][0], 700);|||
|ラムダのreturnは{}の前に-> llなどと指定|||
|vectorで途中からを指す方法ある？配列だとint* a = a_org+3;でいいが→ &v[0] で良いらしい||SRM 683 D1E|
|再起するラムダ式はautoが使えない。 findは複雑。map系は、findが提供されてて、not foundはend()。vectorはstlのfindしか使えず、not foundはend()。stringはfindが提供されてて、not foundはstring::npos||SRM 682 D1E|
|二分探索の構造が00001111じゃないといけないの忘れてた。ちゃんとprintして確かめるように。||SRM 681 D1E|
|topcoderは入力を実装する必要がなく、1-indexに気づきにくいので注意。|||
|複数の要素をソートする時structとか作るのが面倒な場合は、b_[i] = P(b[i], i); sort(all(b_)); index[i] = b_.second;としておいて、rep(j_, b.size()) ll j = index[j_];で擬似的にソートできる。3変数以上のソートを簡略的にやるのに便利。ただ、tupleがそもそも上手くできるので、うーんというかんじ。|||
|ちょくちょくvector<ll, ll, ll> a;でタプルベクトルになる、みたいな記事を見るけど、ならない。きちんとtupleで囲みましょう。|||
|int系気をつけて、超精密に考えましょう||677 D1E|
|topcoderは与えられている変数の型が自分の思ったものでないことがある||676 D1E|
|木は結構自由に形を決められる。∋ー∈とか。||675 D1E|
|辺に注目すると考察が進むことがある（総和は辺*2など）||674 D1E|
|「やりとりが発生しない場所はあるか」という考え方は重要。||672 D1E|
|DPは「選択肢」を考えると良さそう||672 D1E|
|Paiza S02 配る再帰（＝初めから決まっていく再帰）のコツ：集める再帰（＝後から決まっていく再帰）と逆のポイント：(1) 異常条件は、そもそも遷移させない。(2)memoしてから遷移する。|||
|N=100のO(N^4)はtopcoderでは行ける。計算量に余裕があるときにはなるべく全探索する。片方向の市松累積和、みたいなちょっとひねった累積和で計算量が落ちることがある。||SRM 610 D1E|
|INFを使ってるなら、大きさをチェック。|||
|どこかのB 三分探索は、解析的なら微分して二分探索問題にできる。||ARC 50B|
|二部マッチングの全列挙はNP完全。detなら出来るみたいなやつ||ARC 51C|
|どれか1つは変わらない、という発想は良い||SRM 551 D1E|
|今回は問題の性格からして動的計画法な気がします(ゲームの流れ(状態)に応じて戦略を変えるというような感じになるはずなので)。||ARC 55B|
|奇数長閉路がない＝二部グラフ まだ色がぬれる→連結二部グラフ||MUJIN C|
|自明な最大ケースをテストするの大事（今回なら100 1は必ず1のはず、とか）||TDPC D|
|DP 「添字i未満」というより、「i個見た時」と言ったほうが良さそう||SRM 602 D1E|
|遷移をまとめて状態を減らす。この状態からあり得る遷移パターンは？と考えれば自然と見えてくるはず||SRM 602 D1E|
|配るDPの初期化は、「そもそも不可能な状態」というのを表現したいことが多い。したがって、-1で初期化して異常値を表すようなことが必要||SRM 602 D1E|
|意外とvectorのeraseは怖くない||SRM 637 D1E|
|区間スケジューリング系は本当に後ろソートが好きだな…||SRM 645 D1E|
|Topcoderではllにするのを絶対にやらないとダメ|intで渡されてしまうので…|SRM 552 D1E|
|副作用を元の配列に行うときは、非常に注意。||SRM625 D1E|
|文章で書くと、きちんとアルゴリズムを表せてるのに、先にコードを書いてしまうと死ぬ|きちんと解法を文章で書くべき。そんなに時間のかかるものでもないし。|SRM615|
|graphvizとwolfram alphaをきちんと活用しましょう||SRM 691 D2M|
|minの初期値はINF、というわけではない、0とかの可能性もある。ちゃんと初期値は設定。||SRM616|
|mとかnではなくてsizeを使いましょう|複数のvectorが出てくる場合は特にsizeを使わないとミスって死ぬ|ABC 40D|
|意味不明なWA|ランダム入力に対してvalgrindをかけるといいかも|ABC 40D|
|「こっちかこっちの条件を満たす」というフロー。頂点の前に一個合流用の頂点を用意する||Luigi’s Tavern|
|入力が10万を超えたら問答無用でprintf, scanfする|cin/cout/vector -> scanf/printf/生配列 の劇的before after、普通にAtcoderでも2倍くらい変わる！|AGC02 D|
|円環の典型「基本直線だが、一箇所だけ破れる」||魔法少女さやかちゃん|
|メモリ使用量改善すると実行時間も改善されるのはよくある|メモリ確保量, キャッシュの乗り方が違う|低速きたまさ法の勉強中|
|二分探索は必ずバグるので、非常に大きく図を書いて「探索範囲」「具体的なx」「そのxで1になるか0になるか」を書くこと。||Code Festival 2014 予選B D|
|閉区間で考察せよ|人間の頭は開区間でできていないので、閉区間で考察すること|Code Festival 2014 予選B D|
|コンテナにsizeをそのまま突っ込んではいけない|未定義動作らしい|Quest of Merchant|
|int128_tって__builtin_popcountが実装されていない|よほど定数倍高速化したくないならbitsetを使いましょう|Twenty Questions|
|clang++の-fsanitize=undefinedでオーバーフロー検出していても、accumulate(0ll, a.begin(), a.end());のllを忘れるタイプのオーバーフローは検出してくれない|||
|WAしやすい問題だとわかりながらテスト雑にやらない||Codeforces 362 Div.2 B|
|マッチング -> 最大フロー||Luigi's Tarvern|
|区間の管理はsetでやる||Code Festival 2015 予選B D|
|永続、永続は木、木の探索はDFS、木の状態が多い場合はグローバルメモリ||Codeforces 368 D2D|
|TとSのLCP（Tは唯一）は、Zアルゴリズムで構築O(n) 参照O(1)で可能。||Almost Same Substring|
|ループがないならDAG||Merry Christmas|
|Nが小さいグラフはとりあえずワーシャルフロイドで全点にすぐ行けると思う||Merry Christmas|
|「無理やり二部グラフにしたもの」|「2V個の頂点V, V’を用意して、元のグラフx->yに辺があるならばx->y’に辺を張る、としたときの二部グラフ」と定義する|Merry Christmas|
|DAG上での最小パス被覆（全頂点を通るような）は、無理やり二部グラフにしたものの最大マッチングである（典型）||Merry Christmas|
|フェルマーの小定理、分数のmod||AOJ Fast Division|
|グラフ構築ゲーはname server作ったほうがいい||ルイージの酒場|
|__builtin_popcountは使ってはならない！！|__builtin_popcountllを使いましょう。||
|doubleの精度による丸め誤差は大きくもなる||yukicoder 413|
|行列累乗は行列を先に計算するとめっちゃ遅くなるので、行列xベクトルを計算しましょう。||AOJ Three-way Branch|
|構築ありの行列累乗だとメモ化できるので早い||AOJ Three-way Branch|
|5歩とか9歩みたいなのは両側BFS（半分全列挙）が聞く||Reverse Sort, yukicoder 371|
|辞書順は取れるときにとれば最適になる。待っていても長くなって悪くなるし、一回一回で最適なものを選べばいいだけだから||563 D1E|
|Mod構造体のdpはDP配列そのものはintで受けられる。||Hyperrectangle|
|盤面、上書きは後ろから塗りはがして?にしていく||Topcoder 655 D1E|
|確率のDPは条件付き期待値を計算すると良い（つまり今までのことを考えてはならない）||656 D1E|
|一度HackされたりWAが不安ならロックしないで、きちんとテストする||Codeforces 362 D2B|
|木の最短経路はLCA||Codeforces 362 D2C|
|成功ケースの可視化の重要性||Topcoder 631 D1E|
|DP、数値と文字列の比較||Code Festival 2016 トーナメント1回戦 B|
|飛び飛びのDPは速い||CodeFestival 2016 Final E|
|状態が一個しかないDPもある||CodeFestival 2016 Final E|
|状態が一個しかないDPもある||SRM703E|
|Topcoderの速度チェックはサーバで出来る||SRM703E|
|DAGは横に並べて考察||SRM703E|
|recって付けるときは、直し忘れるので、本体の方にもstartなりなんなり付けないと、直し損ねて死ぬ||SRM703E|
|最短パスの部分パスも最短パス||Atcoder ABC 51D|
|頂点xを通る頂点s->頂点tの最短パスが存在→dist(s, t) = dist(s, x) + dist(x, t)||Atcoder ABC 51D|
|辺i=(a[i], b[i], c[i])を通る頂点s->頂点tの最短パスが存在→dist(s, t) = dist(s, a[i]) + c[i] + dist(b[i], t)||Atcoder ABC 51D|
|適当なことを言うと、最短距離問題は、最小性と唱えまくれば正当性が出てきます||Atcoder ABC 51D|
|AとBの最大クリークをつなげると、A*Bだけの辺が増える。||CF385 D2C|
|構築系はassert大事||CF 386 D2D|
|「2番目に大きい」RMQは、1番大きい人をRMQで求めて、0にしたあとに、再度RMQで1番大きい人を求めることで可能。RMQの中での集合無視クエリは、相当するデータを0にすればいいだけ。||CF388 D2D|
|1位は2位のすぐ上||Codeforces 388 D2D|
|配る形でDPを考えるな！！！まず集める方向。||Codeforces 391 D2D|
|DPは、直前の情報だけではなく、今までに計算した全てを使えることを忘れないように。||Codeforces 391 D2D|
|まずは少ない状態でDPを構成する（1変数）ように頑張る。情報が足りなかったら、追加していく。||Codeforces 391 D2D|
|n進数のDPは、今までの桁をn倍すると局所漸化式っぽくなる||Codeforces 391 D2D|
|string->何かは、stollとstodを使う|めんどいのでライブラリ作った。特に、stollはLONG_MAX以上のstringを入れるとREするので、stodでLLONG_MAXより大きい場合を弾く必要|Codeforces 391 D2D|
|反射は展開||Codeforces 391 D2C|
|少なければ盤面で||Codeforces 391 D2C|
|再帰は、「今こんな状態で、今までこうだった」という情報を載せる。|引数は意味論的に二分される|CF391 D2E|
|再帰は、初期値の「今までこうだった」が全て異常値になるという意識が必要。全部-1にするなり、注意力が必要|||
|構築ゲーは微分を見ると良い||SRM 707 Easy|
|必ずコーナーケースは、returnする！！||SRM 707 Easy|
|ちゃんと全探索的に考える。「s b^k + c_0  a b^0 + c_1 a b^1 + … と表現出来る」||SRM707Med|
|重複判定は、全順序を定義する比較関数か、ハッシュを定義するとできる。||Codeforces 388 B|
|Stringのrange forは注意！！！例えば以下だと、最後のNULLも含めて、5回回る。for (char c : "AGCT") counter[c] = 0;|以下のようにしないといけないfor (char c : "AGCT") if (c) counter[c] = 0;|Codeforces 388 B|
|Unordered_mapのカウンターは、候補の初期値に0を突っ込むのをわすれないように。|Range forすると、一回もカウントされていないものが見逃される可能性が有る。|Codeforces 388 B|
|unordered_setというものがある||Codeforces 388 B|
|折れ線で考える||Codeforces Goodbye 2016 C|
|両端を狭めていく考え方||Codeforces Goodbye 2016 C|
|二分探索で行けるかどうかは、まず特性関数を作ったらprintしてみて、大丈夫そうかを確認すること！！！絶対！！||Codeforces Goodbye 2016 C|
|「AとBの共有」を消す場合には、AもBも共有も消さないといけない。||Codeforces 8VC Venture Cup 2017 - Elimination Round B|
|約数の全列挙はO(sqrt(N))で簡単に実装できる||CF 391D2B|
|素因数では1がコーナーケース||CF 391D2B|
|円グラフっぽいやつとかは、極座標||FHC A|
|Atan2はやるまえに事前に第一象限に持ってくる。||FHC A|
|WFで自己ループ検出は簡単|自分から自分への距離が負||
|有向グラフの閉路検出は、pendingみたいな状態を入れないといけないから[[注意>http://www.logos.t.u-tokyo.ac.jp/~tau/lecture/computer_software/gen/slides/8-graph-2.pdf]]|||
|グローバルメモリを逆変換でコピー少なくやるテク、breakとかreturnとかでしばしば戻すのを忘れる…||Topcoder SRM 627 D1E|
|出力の制限について気づけたのはいいけど、こういう発想は常に持っておきたい。||Topcoder SRM 631 D1E|
|絶対にBatch Testはやりましょう。MLEとか防止用||TopCoder SRM 539 Div2 Medium|
|sumを数式できちんと書くとなんか答えが見えてくる||601D1E|
|グローバルメモリを逆変換でコピー少なくやるテク、breakとかreturnとかでしばしば戻すのを忘れる…||Topcoder SRM 627 D1E|
|出力の制限について気づけたのはいいけど、こういう発想は常に持っておきたい。||Topcoder SRM 631 D1E|
|絶対にBatch Testはやりましょう。MLEとか防止用||TopCoder SRM 539 Div2 Medium|
|状態の少ないbitDPは意外と200次元とかでもできてしまう。本質的な状態数を見抜く力大事。||709 Div.1 Med|
|何らかの制限を入れたDPは「矛盾しない」と表現したほうがいい気がする状態の少ないbitDP||709 Div.1 Med|
|解き終わって絶対通したかったら愚直解との比較を書く、問題を精読する特に入力制限||709 Div.1 Med|
|座圧は添字を交差させるとサボれる！||SRM614D1E|
|配るDPでは、DPテーブル全部を走査しなければならない！！集めるDPでは、必要なところまで回せばいいが、配るDPはそうはいかない。||SRM698D1E|
|配る範囲がDPテーブルを超す可能性があるが、余分にdpテーブルを確保しておく方が、配る添字の範囲が超えているかチェックするよりは楽。||SRM698D1E|
|桁DPは下から見るほうがいいかも。桁上がりを扱えるので。||SRM 665 D1E|
|配るDPでは、「dp[i][j][h]」が確定している時、「dp[i+1][*][*]」を確定させようとしている！||SRM 665 D1E|
|繰り上がりがある場合のDPは、繰り上がっていることを覚えておきながらも、値にはきちんと反映させる。||SRM 665 D1E|
|DPはきちんと状態を決めたら、それを図示すること！かならず、状態に応じた必要十分な図がかけるはず。||SRM 665 D1E|
|codeforcesでは、unordered_mapを使わない！！よほどTLが厳しそうで、よほど参加者が当てられる自由度が低い場合でない限り。||CF 400 D2C|
|参加者がunordered killする||CF 400 D2C|
|閉区間は面積を+1するのを忘れがち||SRM623D1E|
|素数個数関数π(x)とは実数xに対して定義されて、x以下の素数の個数を表します。素数定理：π(x)≒x/log(x);別の近似: xが素数である確率は1/log xなので、π(x) = \integral 1/ log(x) dx = li(x)。||yukicoder 371|
|文字列に文字列がヒットする添字を全列挙するのは、普通にfor文で回すべき。めんどいので||Topcoder SRM 663 D1E|
|1-辺切断を切断辺または橋 (bridge) 1本切って非連結になるような辺のこと。||SRM 662 D1E|
|ハミルトン路（全頂点一筆書き）は閉路だろうがなんだろうがNP完全||SRM 662 D1E|
|メンドければ2重ループすれば木のdepthが簡単に求まるよ||SRM 666 D1E|
|範囲素因数分解は結構速い（範囲1000万に対して構築含めて1.5秒くらいで終わる）||661 D1E|
|std::lower_boundをmap系に突っ込むと線形になるのは結構有名で、数々の競技プログラマを奈落へ突き落としてきました(map.lower_boundなら大丈夫|||
|条件が複数ある探索は、それぞれ問題を作って、それの和集合を取る。「事前に決まらない」場合分けはそれぞれ探索して和集合|||SRM 628D1E
|制限付きのDPは、複数制限があるけど、初めにあたった制限のみを展開すると、再帰的に網羅できる。||SRM 653D1E|
||||
||||
||||
||||
||||
||||
||||
||||
||||
||||
||||
||||


Topcoder SRM 658 D1E
Stringのforall
作れないなら-1、みたいなやつがある場合、特に貪欲で構築した場合、「存在するなら構築できる」してチェックが必須！
・WFは初めのループが経由点！！！ループ内でchminで隣接行列を割って実装（覚える）
rep(_, n) rep(i, n) rep(j, n) chmin(g[i][j], g[i][_]+g[_][j]);


SRM598D1E
集合分割って難しいから貪欲多くないですか
Facebook Q1 Bとかも



SRM 630 D1E
木の中心と半径の全探索は任意に頂点を二つ取る

TopCoder SRM 635 Div1 Easy 
・全探索の変数を減らすためには、「他の変数が決まった時、この変数は一意に定まらないか？」と考える。

SRM 642 D1E
・期待値とかは全状態に確率を定義してしまう
・確率と配るDPは相性がいい

LOJ526
・n!でも枝刈りすると結構解ける（18くらいまでは）


SRM 639 D1E
次に、{1, 3, …, 2n+1}でxを作るには、
「引いた結果が2か負でなければ、上から引いていく」という貪欲で構築できるが、知るかという感じ。
→証明

SRM611D1E
・A[i]をBのLCMで構築できる⇔a[i]の約数であるBの元のLCMがa[i]に一致


SRM 709 D1E
勉強したこと
・本当にその状態だけで最適値が確定しますか。逆転しませんか。
・「出力を状態に含む」DP
・maskiみたいに、bit maskはちゃんとmaskと明示したほうがいい（混乱する）
・rep(maski, 1<<a.size()) rep(i, a.size()) if (maski & (1ll << i)) がもらうbitDPのテンプレ
・rep(maski, 1<<a.size()) rep(i, a.size()) if (!(maski & (1ll << i))) が配るbitDPのテンプレ
・bitDPは、maskiに何かのbitを増やしたり減らしたりすると必ず値が増えたり減ったりするので、ループでトポソされているから上手く動く




CF 398 D2C
・重みが負のものを含む場合、0がコーナーケースになりがちなので注意
・DPもDFSもそうなのだが、部分問題をマージするような計算をする場合は、計算したい情報をきちんと言語化し、事前検討することが極めて重要。DFSの場合には、頂点にデータが載っているので、頂点にどのような情報を載せるかを検討して、実装可能性を吟味すること。いい加減に実装を始めない。
・exit(0)で再帰中でもプログラムを抜けられる。
・全頂点にどんな情報を載せるか？というデータ構造みたいなものが決まると、自動的に処理が決まっていく感じがある。どういう頂点に対して何を載せるか、という思考回路が足りてなさすぎるし、何が載っていると嬉しい、みたいな思考回路も足りない。


Codeforces 402 D2E
・N+1でループを回すべきところを、nでループを回して死んだ。
Valgrindではnでやるべきところをn+1なら気づくことができるが、その逆パターンは検出できない。更に悪いことには、n+1をnで回しても、一種の嘘解法になっていて、サンプルが合ってしまうケースが多い。一体どうすればよいのだろうか…？
・これくらいの実装問題になってくると、もはや早解きのために雑に変数を定義するより、コメントをきちんと書いたりテスト駆動的にやったりするほうがパフォーマンスがでるな、ということに気づきました。
・寝起きの僕はつよい。日本に帰ってきてから、意味わからないくらいレーティングが落ちている。  今日は実は昼寝をしてやって、あまりにスムーズにコーディングできてびっくりした。ドイツでは昼で眠くなかったから強かったのかもしれない。



SRM699
勉強したこと
・Xor b_iが既知の時、それを実現する最小のSum b_iは、Xor b_iそのもの。
・XORは偶数奇数と見れる（mod 2の和と同じなので！）
	自分以外のxorが1 = 自分以外が奇数
Xorはそもそも、bool代数の足し算であり、偶奇をコーディングしている。
$$a \otimes b = c \otimes d \Leftrightarrow (a = b \Leftrightarrow c = d)$$


ARC80 Prime Flip
範囲系は累積和を取ると左右の操作になる



Code Festival 2016 Final E
勉強したこと
・飛び飛びのDPは速い
・状態が一個しかないDPもある
・出力の全探索をなぜ思いつかないんですか。倍々ゲーム系はきちんと出力の考察を行う。そうじゃなくてもだけど



Code Festival 2014 予選B D 登山家
スタックでやる方法がある
類題：京都大学2013 カーペット
最大長方形のアルゴリズム

Atcoder 東京大学プログラミングコンテスト2013 C
・単位元をきちんと選びましょう。minだからといってINFとかしていると足元をすくわれる。

AtCoder ARC 57B
勉強したこと
・仮説は持っていたのにそれを実験しないのはもったいない。単調性を実験で探すなどの努力はきちんとすべき。
「みんなのプロコン」本選 2017 C
勉強したこと
・%の代わりにifと-=を使うと早い（特にC++14 (Clang 3.8.0)ではベクタ最適化が結構頭良い）
・平方分割は大概重いので、定数倍高速化を心がける。
・平方分割でのバケットはきちんと見積もって設定する。例えば今回、バケットと裾ので計算の重さが1:2なので、B=250くらいにすると良さそう、とか
AGC 008B
・累積和は開区間だとすごく楽。a[i, j)はasum[j]-asum[i]（マジか）


Codeforces 446 D2D
勉強したこと
・最大値の候補を管理するpriority queue

勉強したこと
・gcdは約数全列挙って何度言えばわかるんですか？
・メモ化は先に（忘れるので）

勉強したこと
・long long -> intは普通に2倍速になる
・これ、ダイクストラでなくてBFSでもできると思ってたができなかった。
・n, mを書き間違えた…HとWなら間違えないかなあ…