競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック 帰着する力をつけるために言語化しつつあったものとかなりオーバーラップがある。
- 入力の制約から考える
- 分解して考える
- 変数を一つ固定する
- 行列の半分
- XとYにわける
- 操作の不変量に注目
- 偶奇に注目
- 操作の順番によらない
- 時間軸反転
- 元に戻せる操作
- 左右から累積積
- 等差数列の加算は差に注目
- 区間反転の合成はXOR
- Grundy数
- 余事象を引く
- k番目の数を二分探索
- XORは繰り上がりのない足し算
- XORは桁ごとに分割可能
- 45度回転
- 差の最小化は中央値
- 代表的なグラフで考察
- 木は二部グラフ
- 木の直径
- 最大化を二分探索で
- 選択肢が少ない方から貪欲
- 二次元座標を二部グラフにする
- 順序を有向グラフにする
- 凸関数の極値は三分探索
- 単調増加ならしゃくとり法
- 等比数列は剰余に注目
- N進数は剰余に注目
- 括弧列は上り下り
競技プログラミングで解法を思いつくための典型的な考え方から言及されている問題を確認していく。