黙ってグラフにしてみよう
探索なら状態空間がグラフ。最適にグループ分け→最小カット。
数論問題なら mod N で N 点グラフ！
二部グラフではないですか
特に二部グラフにならないか注意深く観察しよう。チェス盤白黒など
凸関数じゃないですか (最大値/最小値を求める問題)
最大値/最小値は凸関数なら賢さ不要で数値的に三分探索できる
目的関数を固定する (最大値/最小値を最小/最大化する問題)
「最小値 x にできる？」という問題なら簡単に yes/no 答えられる？
ならば x を全探索。単調ならば二分探索。
前から順に固定する (辞書順最小を求める問題)
「1文字目をaにしたら解がある？ない？」を繰返し１文字ずつ決める
整数でGo!
条件反転してみよう
「○○を満たす物は何個？」 → 「○○を満たさないものは何個？」
εを避ける
期待値ならば線形性
E(aX+bY) = aE(X) + bE(Y)
期待値なら即座に問題を線形分解
小さいところで規則を探す (数学ゲー)
小さい入力を全探索して眺める
巨大なメモ化はmapにしない!
配列にすると20倍は速い
n4
504 ≒ 625万
n5
255 ≒ 1000万
Σ nk
3n
2nC n
≒ nk+1 / k+1
315 ≒ 1500万
26C13
≒ 1000万
≒ 2n / √n