競技プログラミングで解法を思いつくための典型的な考え方 - 西尾泰和の外部脳

競技プログラミングで解法を思いつくための典型的な考え方

競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック

帰着する力をつけるために言語化しつつあったものとかなりオーバーラップがある。

入力の制約から考える

小さい制約の問題

Nが8前後の制約

Nが10~20前後の制約

N が 30~40前後の制約

N が 50前後の制約 O(N^4) OK

N が 300~500前後の制約

N が 1000 前後の制約

分解して考える

小さな定数に注目

変数を一つ固定する

3つのものの真ん中を固定

行列の半分

XとYにわける

操作の不変量に注目

偶奇に注目

偶奇で場合わけ

操作の順番によらない

時間軸反転

元に戻せる操作

左右から累積積

等差数列の加算は差に注目

区間反転の合成はXOR

余事象を引く

k番目の数を二分探索

XORは繰り上がりのない足し算

XORは桁ごとに分割可能

差の最小化は中央値

代表的なグラフで考察

木は二部グラフ

最大化を二分探索で

選択肢が少ない方から貪欲

二次元座標を二部グラフにする

順序を有向グラフにする

凸関数の極値は三分探索

単調増加ならしゃくとり法

等比数列は剰余に注目

N進数は剰余に注目

括弧列は上り下り

競技プログラミングで解法を思いつくための典型的な考え方から言及されている問題を確認していく。