MSTにある辺を使うかもしれないかどうかは、MSTを作ってパスの重みのminと一致するか見る
期待値はまず分解できないか考える
平面グラフのオイラーの定理 $v-e+f=2$
貪欲で最適解が求まるとき、左から貪欲と右から貪欲をすると間はすべてできる
小さいケースで実験する(n=2で表をつくるか、適当なnで実験コードを書く→仮説を立てる)
約数を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が消える
ある配列から要素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のどちらかを固定する
境界について判定する
損失と利益の両方がある場合、利益を全部取ったことにして、損失の方に利益を加える
損失と利益を同時に考えることは(一般的には)難しい
long long でビットシフト →(1LL « x)
順列の置換はいくつかのサイクルのまとまりとなる
新しい数列を作って中央値を求めるという問題
直接は求められないが、中央値が$X$以上(以下)であるか判定する判定問題が解けるならば、二分探索で境界を探すことが出来て、その境界は最大(最小)値
判定問題の解き方は、$X$以上の個数と$X$未満の個数を求め、比較する
最大値の最小化→二分探索
並列二分探索
制約が狭いほうから決めていく
leading-zeroの桁dp
dpテーブルは-1で初期化(遷移できないのかどうか確かめるため)
0初期化するのは、$dp[0][0]$だけ。(0であると確定しているため)
互いに素の数え上げ→包除原理が使える
ある頂点から$X$回操作をした結果を大量に求める→ダブリング($2^0, 2^1, 2^2, \dots, 2^k$回操作をした結果は簡単に求まるので、2べきに分解して考える)
一筆書き(準オイラー路)では、端点だけが奇数次数で、端点以外は偶数次数
複雑な経路を単純な経路の組み合わせに分割する
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)$の組で管理
コストの上限が小さい→コストの和で計算量が抑えられるかも
基底のマージ