プロコン/勉強したこと

編集履歴

プロコン

まとめと例題

方針説明例題
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
一つ前にしか依存しない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
n進数の不定長データ列の生成はqueueを使う(A, B, C, AA, AB, ...など)サンプルコードSRM 682 Div2 Medium
マジックナンバーは消すバグの温床になる
負のDPconst int MAX = 1000; int ary[2*MAX + 1]; int *dp = ary + MAX; // [-MAX, MAX]にアクセスできる!
二段DPSRM 523 Div2 Hard
DPは問題の制約を気にせず解いて，後でまとめるときに制約を考える円卓テーブルで隣り合って同じ色はダメ→同じ色も許容するDPを組んで，後で違う色の場合の数だけ集めるSRM 551 Div2 Hard
単調増加DPは変化分だけを追うDPに変換するYukicoder 269
包除原理全体からある条件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 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-14ABC 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個のみに依存するDPkが小さく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はdoubleSRM 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*=-1ABC05B
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::nposSRM 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
ループがないならDAGMerry Christmas
Nが小さいグラフはとりあえずワーシャルフロイドで全点にすぐ行けると思うMerry Christmas
「無理やり二部グラフにしたもの」「2V個の頂点V, V’を用意して、元のグラフx->yに辺があるならばx->y’に辺を張る、としたときの二部グラフ」と定義するMerry Christmas
DAG上での最小パス被覆（全頂点を通るような）は、無理やり二部グラフにしたものの最大マッチングである（典型）Merry Christmas
フェルマーの小定理、分数のmodAOJ 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
木の最短経路はLCACodeforces 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みたいな状態を入れないといけないから注意
グローバルメモリを逆変換でコピー少なくやるテク、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は「矛盾しない」と表現したほうがいい気がする状態の少ないbitDP709 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⊗b=c⊗d⇔(a=b⇔c=d)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なら間違えないかなあ…

最終更新: 2020-01-01