問題を解いて得た知見
近く整理したい
まだまとめてない奴
最近見たものほど上にある
- MSTにある辺を使うかもしれないかどうかは、MSTを作ってパスの重みのminと一致するか見る
- 期待値はまず分解できないか考える
- 平面グラフのオイラーの定理 $v-e+f=2$
- 貪欲で最適解が求まるとき、左から貪欲と右から貪欲をすると間はすべてできる
- 小さいケースで実験する(n=2で表をつくるか、適当なnで実験コードを書く→仮説を立てる)
- 1~2次元で、法則に従ってグリッドを動く問題などは実験が有用、コーナーケースを網羅しやすい
- 約数をvectorに入れるやつは$M=10^6$ですら危ない
- ナップサックの半分全列挙→マージソートで余計なlogがつかない
- ゲームdp
- 基本は逆から求めていく
- 手番によって目的が違うことに注意
- bitwise xor/or/and の問題はbitごとに独立に考えた方が見通しがいい
- 括弧列の問題→二値化 or stack
- 制約が$n \le 10^9$のときintを使わない
- 偶奇に注目すると漸化式っぽくできることがある
- 絶対値は場合分けやソートで外す
- 偶奇に着目することでできる可能性がある
- nのk進法の桁和がk-1の倍数⇒nはk-1の倍数
- 奇閉路が存在しない⇔二部グラフ
- 二部グラフ判定は頂点を倍にしたUnion-Findでできる
- (a, b)に辺がある→(a, b+n), (a+n, b)をuniteする
- aとa+nが同じ集合にあれば二部グラフではない
- 最短路を求めるときに、コストの上限が小さければstackでlogが消える
- ARC 061 E(辺の引き方を工夫する必要がある）
- ある配列から要素1つを除いてできるかどうかを判定→左からと右からの2つでそれぞれiまで使ったとき～のdpをする
- 逆操作を考える
- ゲーム問題
- すべてが0の状態から逆算する
- →偶奇性、xorなど
- 真似戦略、点対称の位置に置く
- 相手に負けの状態を押しつける
- N=0, 1を確かめる(コーナーケース)(N=0は特にcodeforcesで頻出のコーナー)
- 文字列の辞書順最小→suffixから順にdp
- マンハッタン距離: $(x, y) \mapsto (x+y, x-y)$と変換
- 配列に変更を加えて探索するとき、配列のコピーを避けるためには配列を変更→dfs→配列を戻す
- scanfでchar*を読む → scanf(“ %c”, &a) などと空白を開ける
- 連結成分→union-find
- 頂点を2つに分類→最小カット？(燃やす埋める)
- 1個決めると全部が決まる
- max{A} -min{A}の最大化(最小化)→maxとminのどちらかを固定する
- Codeforces Round #535 (Div. 3) - E1 (maxを固定)
- 境界について判定する
- 損失と利益の両方がある場合、利益を全部取ったことにして、損失の方に利益を加える
- 燃やす埋める問題
- 損失と利益を同時に考えることは(一般的には)難しい
- long long でビットシフト →(1LL « x)
- 順列の置換はいくつかのサイクルのまとまりとなる
- 順列でなくてもサイクルの考え方を使うことがある
- ある2要素をswap⇔サイクル数が1増えるか1減る
- 新しい数列を作って中央値を求めるという問題
- 直接は求められないが、中央値が$X$以上(以下)であるか判定する判定問題が解けるならば、二分探索で境界を探すことが出来て、その境界は最大(最小)値
- 判定問題の解き方は、$X$以上の個数と$X$未満の個数を求め、比較する
- 最大値の最小化→二分探索
- 最大値が$X$以下になるかどうかの判定問題が解ける場合に有用
- 並列二分探索
- 普通に考えるとクエリごとに操作をしなければいけなく、$O(NQ)$とかになる時に使う
- クエリを先読みし、範囲を記録しておき、中間について順に判定をする二分探索をして$O((Q+N)logN)$
- 制約が狭いほうから決めていく
- leading-zeroの桁dp
- dpテーブルは-1で初期化(遷移できないのかどうか確かめるため)
- 0初期化するのは、$dp[0][0]$だけ。(0であると確定しているため)
- 互いに素の数え上げ→包除原理が使える
- 6と互いに素→(数の集合)-(2の倍数)-(3の倍数)+(6の倍数)
- ある頂点から$X$回操作をした結果を大量に求める→ダブリング($2^0, 2^1, 2^2, \dots, 2^k$回操作をした結果は簡単に求まるので、2べきに分解して考える)
- 一筆書き(準オイラー路)では、端点だけが奇数次数で、端点以外は偶数次数
- みんなのプロコン 2019 D(始め、終わりを最大値、最小値と同じにすると考察に失敗する)
- 複雑な経路を単純な経路の組み合わせに分割する
- 1次式の累積和(1, 2, 3, 4, 5 …を範囲に加算するなど)をするには、ax+bで配列を2本持つと見通しがいい
- これだとオーバーフローする場合があるので注意が必要
- マンハッタン距離なら、縦横独立して考えられる
- 不変量に注目する
- 最大長方形→縦方向に「上に白が何個連なっているか」を見て、横1列ずつに、ヒストグラムの最大長方形の考え方を適用する(蟻本テク)
- $X$の倍数→$0\mod X$
- 最下位ビットを取り出す→x&-x
- 重さがX以下なら重さにYを加算する→X+Yでソート
- 最小カットにできる→削除するものは辺
- 貪欲→任意選択
- $x^p \equiv x \ \ (mod \ p)$(フェルマーの小定理の変形)
- 境界を全探索
- 区間を二分探索→ダブリングが便利
- setを使うとならしでlog
- gcdは階差を取っても累積和をとっても不変
- $\min(|x+y|,|x-y|)$,$\max(|x+y|,|x-y|)$は、xとyの符号を変えても不変
- 最初の要素だけに注目してみる
- 区間スケジューリングをクエリで→ダブリングで出来る
- $n$で割った商を見るときは、 $\lfloor \frac{n}{i} \rfloor$が同じグループでまとめる
- ちょうどK回=(k回以下)-((k-1)回以下)
- すべての場合のfの総和→fがk以下になる組み合わせを計算
- $f(a_i) = f(a_j)$ となるように変形すると簡単に数え上げられる
- 普通のグラフを木にしてみると解ける
- $4n \oplus 4n+1 \oplus 4n+2 \oplus 4n+3=0$
- 足し算だけのときの操作回数→逆から見ると引き算になり簡単に求まる
- 偏角でソートするとうまくいく
- 二項係数が絡むときは和を$N$までにすると総和を交換しやすくなる
- 配るDP→形式的冪級数に変換
- 見る区間が交差していない(完全に含まれるか全く交差しないかのどちらか)のとき、dpをstackでできる。
- 2点$(x_1, y_1), (x_2, y_2)$を通る直線を管理 → $a = x_2-x_1$と$b = y_2-y_1$→aとbをgcdで割る→$c = x_1*b- y_1*a$として$(a, b, c)$の組で管理
- 方程式を整理すると$bx-ay = bx_1 - ay_1$になる。
- コストの上限が小さい→コストの和で計算量が抑えられるかも
- 基底のマージ
for (auto i : a) {
for (auto j : b) i = min(i, i^j);
if(i) b.emplace_back(i);
}
l = 1
while l <= N
r = N / (N / l) + 1
// [l, r) は商が等しくなる区間
l = r
- 区間の長さ$k$において和が正→区間の長さ$2k$において和が正
- ゲーム問題では、順番は無視できない
- 長さ$N$の回文の部分文字列として現れる回文の種類数は高々$N$
- $X$から$Y$までの$M$の倍数の個数は$\lfloor \frac{Y}{M} \rfloor - \lfloor \frac{X-1}{M} \rfloor$