コンテストやバチャ等での失敗を懺悔します
一般的な話
- 部分問題(や,制約を弱めた版)ですら,これでしか解けない → それに近いアルゴリズムを使う
例題:
例題:
- swapをすることで区間を連続にする → $B_i:=A_i -i$ の置換をした上で, $B_i$ を一致させると考えると筋が良い。
例題:
bit
bit 毎に見てもよい
クエリの順番が bit 毎に独立なことがある
期待値関連
- 総和の期待値 -> $i$ 以上の個数の期待値を $i$ を動かして足し合わせる。 決めうち二分探索とお気持ち的には近いかも、忘れがち。
例題:
- 終了までの期待値などでも、ここに操作をする回数の期待値の和 という期待値の線形性が使える
期待値の線形性!(素振り)
例題:
最適化関連
- 実は自明な上界 or 下界が達成可能です!!!!!!!!!! ←解けない時には一回疑う!!!
例題: atcoder.jp
- gcdは,一つ決めれば候補はその約数のみ $ 10 ^ 9 $ 以下の高度合成数の個数は $1344$ 個
例題: atcoder.jp
- 最適化であっても,最終形の判定問題を最初に考えるとうまくいくことがおおい.
例題:
- 絶対値の最大化 は max$(x,-x)$ の最大化で言い換えるとうまくいくことが多い.
動的計画法関連
bitset高速化でもしない限りbool配列でDPは基本的に良くない 何か情報を持たせたい
DPの遷移で、使用しない場合の chmax(dp[i+1][j], dp[i][j]) みたいなのを忘れない!!(やらかしが多い)
結果としてありうるか状態を判定する -> 判定問題は貪欲にできる -> 貪欲法をDPに落とす の思考をスムーズに出来るようにする
例題:
https://techful-programming.com/user/event/session/I1Hs4VIF/problem/coding/18306
計算量関連
- 素直な全探索$ Ο(N ^ 2) $ が間に合うなら,まずそれを試す.
例題:
- 調和級数も疑ってみる(特に数列がdistinctだったりする時)
例題:
置換関連
- $i$ から $p_i$ に有向辺を貼って考えるとうまくいくことがおおい.(2点swapなどでも)
例題:
実装関連
bitのi番目を取る時の bit >> i & 1 この & 1 を忘れない!!! (もはやライブラリ化したほうがよくないか?)
メンタル面
- 落ち着く
- 冷静になる