競技プログラミングの考察テクニック
雑多に書いていく予定です。
一般
最終的な状態を考えて逆算する
とても基本的な考え方です。
自分で小さなケースのサンプルをつくって実験する
必要条件で絞り込む
なにかを決め打ち (して探索) する
基本的です。なにかのポイントに気づくのが肝になる問題は多々あります。最大最小値を求めるときに仮の値 k を定めて、二分探索で条件を満たすか満たさないか調べることで最大最小値を求めるテクニックも似たところがある気がします。
2変数を独立に考えていく。
x, y座標上や数列上で考えるときに多い印象です。
制約の厳しいところから考えていく
3 点選択は、真ん中を固定して全探索する。
数を p 進数で表現する。
1 ~ n までの整数を表現 / 構築する必要がある時、p 進数で考えるとよい場合があります。10 進数で表現するよりも p 進数で表現するほうが効率よく(=少ない情報量で)表現できるためです。
前から上書きは、後から確定できる。
数列
nつの要素の数列 a[n] 上で「ある 1 つの要素に A を加え、その他のすべての要素に B を加える」 という操作
「a[n] のすべての要素に B を加え、ある 1 つの要素に A-B を加える」という操作、と言い換えるとうれしいことがあります。
2変数は片側固定して全探索する。
数列上の区間 [i, j] を満たす個数を数えあげる際によく出てくる印象です。 i, j でナイーブに全探索するとO(N2)になるところを、i を固定して条件を満たすものを O(logN) ないしは O(1) で数えることで全体の計算量を落とせます。
累積和はABCで頻出です。
条件を満たす区間和の個数をBITで求める。
数列の区切り位置をBITのindexと見ると、BITの点更新と区間和を求める問題に帰着します。
条件を満たす区間を求めるにはしゃくとり法が有効
グラフ
到達可能判定には DisJointSet が有効
逆向きに条件に合わない点を削除する
構築
構築はサンプルを捨てる
解法を隠すためのダミーであることが多いです。
なるべく機械的な手順を探す
特定の場合のみに通用する構築パターンではダメなので、どんなパターンでも通用するような機械的な構築手順が解になることが多いです。
クエリ
クエリを逆順に処理する
