プロコン

まとめと例題 †

方針説明例題
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<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-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

Codeforces 362 D2B ・一度HackされたりWAが不安ならロックしないで、きちんとテストする

Codeforces 362 D2C ・木の最短経路はLCA

Topcoder 631 D1E 成功ケースの可視化の重要性

↑

面白い部分問題 †

  • 石のやりとりは右から石を流していって、abs(流れた石の量)によって計算できる
  • フィボナッチで自然数が作れる
  • ソートされた一次元の点x_iがあり、その中で全点との距離が最小な点はx_{[n/2]_l}
    部分問題解法解説
    $x_i (i = 0...n)$に対して、$\Sigma abs(x_i - l)$が最小となる数lを求めよ中央値を求めるだけでいい（平均値ではない！）左右見て数が多い方があればそっちに移動したほうがいいので。1,2,5,8なら[2,5]の全数字が解、1,2,8なら2だけが解。
    $ax+y=c (x \in [0, X], y \in [0, Y])$なるx, yは存在するか？するならば一つ挙げよxを[0, min(X, c/a)]の範囲で二分探索(c-ax<=YならOK)。minを取ると、yが0以上という条件が必ず満たされるようになるので、特性関数が単調になる！
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS