つちのこの日記

競プロと音ゲーがメインです。

懺悔一覧

コンテストやバチャ等での失敗を懺悔します

一般的な話

  • 部分問題(や,制約を弱めた版)ですら,これでしか解けない → それに近いアルゴリズムを使う

例題:

atcoder.jp

  • 区間に対する操作や区間和など -> 累積の二要素への作用or演算の言い換えを考える

例題:

atcoder.jp

  • swapをすることで区間を連続にする → $B_i:=A_i -i$ の置換をした上で, $B_i$ を一致させると考えると筋が良い。

例題:

atcoder.jp

bit

  • bit 毎に見てもよい

  • クエリの順番が bit 毎に独立なことがある

期待値関連

  • 総和の期待値 -> $i$ 以上の個数の期待値を $i$ を動かして足し合わせる。 決めうち二分探索とお気持ち的には近いかも、忘れがち。

例題:

atcoder.jp

  • 終了までの期待値などでも、ここに操作をする回数の期待値の和 という期待値の線形性が使える

期待値の線形性!(素振り)

例題:

atcoder.jp

最適化関連

  • 実は自明な上界 or 下界が達成可能です!!!!!!!!!! ←解けない時には一回疑う!!!

例題: atcoder.jp

  • gcdは,一つ決めれば候補はその約数のみ $ 10 ^ 9 $ 以下の高度合成数の個数は $1344$ 個

例題: atcoder.jp

  • 最適化であっても,最終形の判定問題を最初に考えるとうまくいくことがおおい.

例題:

atcoder.jp

atcoder.jp

  • 絶対値の最大化 は max$(x,-x)$ の最大化で言い換えるとうまくいくことが多い.

atcoder.jp

atcoder.jp

動的計画法関連

  • 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) $ が間に合うなら,まずそれを試す.

例題:

atcoder.jp

  • 調和級数も疑ってみる(特に数列がdistinctだったりする時)

例題:

codeforces.com

置換関連

  • $i$ から $p_i$ に有向辺を貼って考えるとうまくいくことがおおい.(2点swapなどでも)

例題:

atcoder.jp

実装関連

  • bitのi番目を取る時の bit >> i & 1 この & 1 を忘れない!!! (もはやライブラリ化したほうがよくないか?)

  • if(i == j == k) とか書かない! C++pythonじゃありません!!

メンタル面

  • 落ち着く
  • 冷静になる