🤯

競技プログラミング：考察の種

に公開
競技プログラミング
tech

AtCoder/Codeforcesのアルゴリズムコンテスト向けに、時々見返して持ち球を忘れないようにするためのページです
随時更新しています。

一覧

前提

何においてもまず誤読に気を付ける

一見悪い計算量の方針

盲点になりやすい

  • 単に制約が小さい(よく見よう)
    • グラフや配列は大きいけど1\leq K\leq10とか書いてあってO(KN\log N)などになる
      • 超頂点、Kごとにデータ構造を作る、距離Kまで探索など
  • 見た目ほど計算量が悪くない
    • 2重ループだけど調和級数、あとエラトステネス
    • 3重ループだけどO(N^2) 二乗の木DP ABC287F
    • for文だけ見ると×だが鳩ノ巣原理で早期脱出が保証される
  • 計算量は悪いけど高速化できる
    • 操作が反転やpopcountで表せるならbitsetを疑う ABC348F
  • 平方分割で計算量が悪いケースを避けられる
    • パラメータが小さい時だけ使える解法と大きい時だけ使える解法がある ABC335F
  • 要素は多いけど要素が持つ値や状態のバリエーションが少ない
    具体例
    • 32bit非負数列Aの累積OR/累積AND 端を固定したとき出現する値は高々32通り
    • 値0~9の出現回数の偶奇(1024通り) ABC295D

ペアの典型

他に考察ステップがあると見えづらくなったり途方に暮れたりする

  • 2次元平面上の座標(x,y)と見なす
    • 平面走査と合わせて"xが小さくyが大きいもの"とか"長方形の面積"に帰着 ABC346G
  • 辺と見なす
    • 連結性判定に帰着する ABC181F
    • 牛ゲーに帰着する(型を覚えてないと無理 x_v-x_u \leq d型の制約に注意) ABC216G
      • 不等式制約の書き換え、発見 ABC404G
        x_v-x_u = d \rightarrow x_v-x_u \leq d \land x_v-x_u \geq d
        正の整数列 \rightarrow S_i-S_{i-1} \geq 1 (S := 累積和)
  • 頂点と見なす
    • 普通に超頂点を作ってBFSとかで最短経路求めるやつ ABC394E

そもそもペアを見出す部分に発想がいるものの例

  • 2点の隙間を通れるか ABC181F
  • 点そのものではなく、x座標の集合とy座標の集合の二部グラフ ABC131F
  • 回文で同じになる2字 ABC394E

操作列の典型

順番がどれくらい重要かで系統が分かれる

  • 順番が関係ないとき
    • (選ぶ問題のとき)何らかの基準でソートして良いものから選ぶ
    • 計算しやすい順番に並べ替える → Mo
  • 順番は関係あるが、後で決めても良いとき
    • (選ぶ問題のとき)操作をストックしておき必要になった時に最適な操作を選んでいたことにするABC344F
    • クエリ平方分割 \sqrt{Q}個ずつまとめて処理する ABC350G
  • 順番が関係あるとき
    • 操作の影響範囲を変更する
      • 範囲に対する操作を境界に対する操作に言い換える
        簡単なところで区間加算→imos、部分木の根に作用→DFSなど　遅延伝搬も同じ発想
      • 対象への操作を、全体への操作+対象以外への逆操作に言い換える ABC398D
    • 操作を分解する
    • 結果が以前の操作に依存しなければ、後ろから見る
    • i-1番目以前とi+1番目以後の干渉を気にしなくても良いなら、i番目で区切る(区間DPみたいにするも良し、順方向の結果と逆方向の結果を繋いでも良し)
  • 操作が多すぎるとき
    • functional graphになっているか = 操作が状態だけで決まるかを確認
      • 状態が少ないときは周期性もしくはダブリングを用いる
        • 一見functional graphでないもの ABC377E
      • 互いに干渉し合うもののみグルーピングする ABC219F

求値の典型

まとめたい

DPの典型

まとめたい

  • 求値の典型と同じく、求めるものを言い換える
    • 要素についての走査→要素が取る値についての走査
      \sum_{i\in S} f(i) = \sum_{v} v\timesnum(i\in S | f(i)=v)
  • 切れ目を全部試す
  • 戻すDP ABC321F

整数の典型

  • 桁が大きすぎる場合、何らかの値でmodを取って代表させる
    • 個別の値に興味がない場合: 状態をまとめてDPをする
    • 個別の値に興味がある場合: 複数の素数の組合せで確率的に一致させる ABC339F

グラフ化の典型

明示的にグラフと言われていないものをグラフとして解く
他の典型と重複しまくり

  • 順列：巡回置換ごとに考える
    • 周期の最小公倍数 回移動すれば、どの点から出発しても必ず元の位置に戻る
  • 大小関係：小さい要素\rightarrow大きな要素への有向辺を張る
    • 大小関係を満たすようにできるか？はDAGになっているか？と言い換えられるABC277F
  • ペアの典型で書いたもの
  • 高度典型で書いたもの(2-SAT、フローに帰着)
    適宜追加

簡略化の典型

ABCの中ではad-hoc感があるもの

  • 一見複雑な形状だが矩形で考えても良い ABC347F
  • 隣り合った要素だけに注目しても良い ABC404E

忘れやすい事実

  • 約数の数(少ない) 10^9までなら1,344個以下、10^{18}までなら103,680個以下
  • 素数の数(多い) 10^9までなら50,847,534個以下 素数定理 \pi(x) \approx x/\ln(x)
    → 競プロで扱うレンジの数に対しては1桁落ちる程度
  • 素因数の種類数(めちゃくちゃ少ない) 10^9までなら8種類以下、10^{18}までなら15種類以下参考
    個数切り詰めて使う場面がありそう
  • その他、良い感じの大きさになるパラメータ
    • 分割数 n=50で204,226
    • 階乗(順列全列挙) 9!=362,880
    • 組合せ _{20}C_{10}=184,756
  • 0は平方数 ABC324D
  • 単純パスの列挙はO(N!)
  • 二項係数を全部足すと2^n、奇数番目or偶数番目だけなら2^{n-1}
  • 写像十二相は考えるよりカンペを見た方が早い
  • 二部グラフであるもの: 木、矩形グリッド(三次元でも)など 「奇閉路を持たない」とも表現される
    • ハニカムグリッドは二部グラフではない
    • 「立方体グラフ」はグラフ理論の用語で、現実の立方体とはちょっと違う
  • グラフの次数に関する性質
    • 次数の和は辺数の2倍
    • サイクルグラフ: 全ての頂点の次数が2(かつ 連結) ABC404C
    • オイラー路の存在条件(準オイラーグラフ): 奇数次の頂点が0個or2個
    • オイラー閉路の存在条件(オイラーグラフ): 奇数次の頂点が0個
    • functional graph: 全頂点の出次数が1
  • 「○○の定理」の類
  • 達成するまでにかかる回数の期待値 = 1回以上かかる確率 + 2回以上かかる確率 + ...

高度典型

解けなくても困らない場面は多いが、時々刺されて泣きを見る

  • 畳み込み ABC392G
    形式的べき級数の考え方と相性が良い
    値を次数、出現回数を係数とした多項式を作る→多項式の積が全組合せの通り数になる
    \sum_{i}n_{i}x^i \times \sum_{i}m_{i}x^i = \sum_{i}k_{i}x^i としたとき、
    • k_{i}は1つ目の式と2つ目の式から値(次数)を1つずつ選んだ和がiになるような選び方の総数
    • k_{i}=\sum_{j\in [0,i]}n_{i-j}m_{j} で、nとmの畳み込みになっている
  • フロー
    • ABC239G ABC320G
    • 特に、燃やす埋める(Project Selection)と呼ばれるもの ABC326G ABC347G ABC193F 典型90 040
      一般に表せるのは一点の割当に対して報酬/コスト、二点の割当が異なる時のコスト(これを使って"aを選ぶにはbを選ばないといけない"を表せる)
      一般には解けないけど追加の制約があれば解けるパターンを知っておく
      • 二点の割当が同じ時のコスト
        → どちらかの頂点の意味を反転させればOK(反転させるものとさせないものが二部グラフなら使える)
      • 3点以上の関係に関するコスト
        → 1つ以上がcならコスト、全てcなら報酬、の形ならOK
        複数頂点への制約を表す超頂点を作るのは典型?
    • Dinic法の時間計算量は押さえ方が色々あり、制約次第で意外と小さくなる
      辺数|E|、最大流Fに対しO(F|E|)や、二部マッチングで頂点数|V|に対しO(\sqrt{|V|}|E|) など
      |E|の成分は必ずかかる(当たり前)
  • 文字列系(そんな高度扱いじゃないかも)
    • 加工してからz-algorithmやSA-ISなどをやる
      • 反転
      • 連結
        • その際にダミー文字を挿入(元の文字列@反転文字列, a@b@c@dなど)
          Suffix Arrayなどで共通部分列を出したりできる
      • substringを1つの文字列として扱う
    • ただ殴れる
    • 似たようなやつの一覧
      • z-algorithm: 各iを始点とする先頭との最長共通部分列
      • KMP: 各iを終端文字とする先頭との最長共通部分列
      • Manacher: 各iを中心とする最長回文
      • EERTREE: 各iを終点とする最長回文
      • suffix array: 各iを始点とする接尾辞を辞書順ソートしたもの
    • 考え方？
      • 接頭辞と見たらTrie, Rolling-Hash, z-algorithmなど色々思い浮かべてみて楽なものを選ぶ
      • 沢山連結するのは名前付きアルゴリズムよりDPを疑う
  • 最小シュタイナー木問題 出所はだいたいこれ
    bitDP解法は性質上、ターミナル\cup{任意の1点}を連結させる時の最小コストが求まる ABC364G ABC395G
  • 並列二分探索 ABC394G ABC233G
  • 2-SAT a \Rightarrow bでSCC分解、とだけ覚えると使えない 必ず乗法標準形(a \lor b) \land (c \lor d)...を作ってクロージャa \lor bを\lnot a \Rightarrow b \land \lnot b \Rightarrow aに変換する
  • 離散対数問題 x^k \equiv y mod mや、f^N(x)=y型の問題はBaby step giant stepを疑う ABC270
  • 高難易度木問題を解くテクニック集
    • パスが沢山あって、全パスについて何かしろ→重心分解 ABC359G 提出
      注目する部分木の処理: 重心の探索(DFS2回) → 重心の隣接頂点からDP → 各部分木に移動 の流れ
  • 有理数の二分探索はStern-Brocot木 ABC333G 提出
    • 実数の二分探索を有理数の二分探索でできるやつ ABC324F ABC294F

軽めの典型問題

で悩まないようにしたい

  • 最長パスはトポロジカルソートの要領
  • 最短閉路は辺を決め打って削除→最短経路、全点対最短経路→往路+復路など

何となく見えた方針に囚われない

  • ABC417D よく見る「区間[L_i, R_i)だけ通過できるやつ」の亜種と思って境界を考えようとすると駄目

その他 未分類

  • 乱択 心の片隅に置いておく ABC339F ABC422E
  • インタラクティブ
  • 約数系包除で混乱する時はメビウスの反転公式から出発する ABC304Fでの応用
    F(n) = \sum_{d|n}f(d) のとき
    f(n) = \sum_{d|n}\mu(\frac{n}{d})F(d)
  • n個のA, m個のB, k個のCの並べ方であって全てのAは全てのBの左側にあるものの通り数ABC405E
  • 連結した文字の辞書順 ABC225F
    • S+T<T+Sでソートして考える(これは全順序で、比較関数として機能する)
    • 前から連結すると壊れる(大小関係が今まで作った文字列の長さに依存)ので後ろから連結する(新しく連結する文字列の長さのみに依存)
  • 斜め累積和 ABC265F
  • 超有名問題を一部改変しただけ、は元の超有名問題の解法に気を取られると良くない ABC408E

その他 思考の癖に気付く

典型を当てはめるだけ、組み合わせるだけ、と言われることでも自分には降って湧いたように見える場合がある

  • パスを扱う木DPをする時、個別のパスに注目する → パスの本数でまとめるDPに気付けない
  • bitDPをする時、TSPや順列のイメージから出発する → 要素番号の昇順に見る遷移ABC352Fに気付けない
  • どでかい素数は陽に求めないと決め付ける → 区間篩に気付けない

Discussion