競プロ公式集（水〜青ver.） - あるたいるの競プロ手記

こんにちは、あるたいるです。自分用に、コンテスト中の方針でまずは確認したいことをまとめた公式集を作ります。書いとかないと忘れちゃうので。例題は一応載せていますが、この解法の限りではなく、僕の感性によります。随時更新します。

考察全般に関するテクニック
DPに関するテクニック
グラフに関するテクニック
整数問題に関するテクニック
- 　Nを整数に分割すると、その値は O(√N) 種類 / 途中から主客転倒
幾何問題に関するテクニック
- 　極端な場所だけ調べる
- 　点の集合は重心を追う
ゲーム系問題に関するテクニック
- 　終状態を考える
- 　交互なら基本的に先手の方が強い
構築系問題に関するテクニック

考察全般に関するテクニック

　決め打ち二分探索は「解を決め打ちすると線形で判定できるとき」に使う

　結構忘れがちである。にぶたんしたのに元の問題の貪欲解を探ろうとしちゃうとかしょっちゅうやる（僕だけかも）。あくまで解を決め打ちしたときに何か嬉しいことがないと意味がない。

　例: ABC227-D など

　2変数の操作は座標系に落とし込む

　2つの対象に対して操作を施す時、それぞれを $x,y$ に対応させて平面座標上で考えると嬉しい性質が見えてくることがある。

　例: ABC059-D, ABC205-E など

　区間+反転はbitが入れ替わる地点について考える

　ある区間についてbitを反転するタイプの問題は、 $s_i$ と $s_{i+1}$ が異なる地点についてのみ考察すれば十分なことがある。特に、 $s_i$ のみ反転させたいとき、 $[s_x,s_{i-1}$ ] と $[s_x,s_i$ ] （あるいはその反対）をセットで行えばよい。

　例: ABC083-D, JSC2019qual-C など

　xorに関する等式/不等式を利用して言い換える

　xorはうまく式変形することで別の式に言い換えられる場合がある（逆もまた然り）。 $x + y = (x\:xor\:y) + 2(x\:and\:y)$ は有名。このことから、 $x\:xor\:y \leq x + y$ もいえる。また、xorで畳み込みを行うときには掛け算に書き換える必要があるので、 $x\:xor\:y = x\: \times \sim\! y \: + \sim\! x \times y$ なども使うことがある(bitwise)。

　例: ABC238-D, ABC098-D, ABC196-F など

　要素の寄与を考える（主客転倒）

　スコアの数え上げでよくやる。特に、経路・順列など、普通に数え上げるのは大変なものに対して適用することが多い。

　例:

　とりあえずDPできないか考える

　よくわからない問題は大体DPである*1。

　明らかに実装量が多すぎるときはそのまま突破しようとしない

　特にAtCoderでは、基本的にめちゃくちゃな実装問題は出ない*2。実装量が多くなりすぎるときはそのまま実装せずもっとうまい別の方針を考え直した方が、結果的に早く解き切れることが多い。脳死のときはよくわからずに実装を始めてしまうことがあるので注意。

DPに関するテクニック

　いったん計算量の悪いDPを考えてみる

　制約的に $O(N^2)$ しか通らないと分かっていても、いったん $O(N^3)$ とか $O(N\,2^N)$ とかのDPで考察する。しばしばそれを高速化することで通せる。

　DPの高速化まとめ

累積和・セグ木・BITなど
　 $O(N^2)$ を $O(N)$ や $O(N\log{N})$ に落とすことができる。特に遷移が $O(N)$ のときよく現れる。言わずと知れた高速化。累積和で通るときは大体セグ木でも通る*3ので、セグ木の方が楽チンである。
例:
「実質同じ」要素を考え、いらない情報を削る
　うまくやると、 $O(2^N)$ を $O(N)$ に落とせたりする。例えば、「最後の要素より大きいものの個数」など、いらない情報を削ぎ落とせないか考える。逆に言うと、情報を削ると解けなくなる場合は方針が間違っている可能性が高い。
　例: ABC232-E など
貪欲と組み合わせる
　貪欲（ソート）と組み合わせて最適な遷移を限定することによって、計算量を大きく削減することができることもある。順列数え上げの場合は、小さい数から決めていくのが典型。何をしたらいいか全くわからないときは貪欲の性質が見えていないことがよくある。
　例: ABC163-E など
インラインDP
　変更箇所が少なく、多くの要素がただ保存されるだけのとき、 $O(N^2)$ を $O(N)$ に落とすことができる。頭がバグりやすい。更新順序に注意。
　例:
行列累乗
　操作回数が遷移に影響しないとき、行列累乗で高速化できることがある。
　例: ABC204-F など
「最後にまとめて計算」を「逐一計算」にする
　「 $dp[i][j] :=$ $i$ 番目まででちょうど $j$ 個使って〜」「最終的な答えは $\sum_{j} dp[N][j] \times f(j)$ 」みたいな時、採用するたび $f$ を作用させることでうまいこと計算量を落とせるパターンがある。
　例: ABC169-F など

　「一番若い番号のものはかならず使う」ことにしてダブルカウントを防ぐ

　見出しの通り。

　例: ABC180-F, ABC226-F など

グラフに関するテクニック

　「最長路」は木なら直径、DAGならトポソしてDP、そうでないなら-1倍してベルマンフォード

　最長路を求めるのは難しい。ただし、特殊なパターンがある。グラフが木ならばBFSを2回で直径（辺素な最長路）が求められる（最終手段としては、全方位木DPによる脳死解法も検討すべき）。DAGならばトポロジカルソートをすることによってDPができる。どちらにも当てはまらないが、 $O(NM)$ が許されるとき、辺の重みを-1倍することでベルマンフォード法を用いた最短路問題に帰着できる。

　例:

　移動に制限がある最短路問題は頂点倍加

　移動になんらかの制約があったり、愚直に辺を貼ると辺数が多くなり過ぎてしまう場合、頂点数を増やして移動に対応させたり、「移動中」に対応するグラフを考えて元のグラフと接続することで高々定数倍に落とせることがある。

　例: ABC132-E, ZONe2021-E など

　木の2頂点間パスに対する操作は根を使って分解

　木の2頂点 $i-j$ を結ぶパスに対して何らかのクエリ（特に偶奇性に関係するもの・xorとか）を作用させるとき、 $root-i$ と $root-j$ に対する操作として分けて考えても同値となることがある。ちなみに、これは区間に関するクエリにも同じことが言える（ $0-i$ と $0-j$ に分解できる）。

　例: ABC201-E, AGC014-B など

整数問題に関するテクニック

　Nを整数に分割すると、その値は O(√N) 種類 / 途中から主客転倒

　正の整数 $N$ に対し、 $x = \lfloor N/i \rfloor$ の値は $O(\sqrt N)$ 種類ほどしかなく、しかも $\sqrt N \lt i \leq N$ でその値は $1 \leq x \lt \sqrt N$ を連続的にとる。そのため、 $\sqrt N$ の前後で主客転倒してまとめて計算をするとうまくいくことがある。