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

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

一覧

一見悪い計算量の方針

盲点になりやすい

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

ペアの典型

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

• 2次元平面上の座標$(x,y)$と見なす
  • 平面走査と合わせて"$x$が小さく$y$が大きいもの"とか"長方形の面積"に帰着 ABC346G
• 辺と見なす
  • 連結性判定に帰着する ABC181F
  • 牛ゲーに帰着する(型を覚えてないと無理 $x_v-x_u<d$型の制約に注意) ABC216G
• 頂点と見なす
  • 普通に頂点倍加してBFSとかで最短経路求めるやつ ABC394E

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

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

操作列の典型

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

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

求値の典型

まとめたい

DPの典型

まとめたい

忘れやすい事実

• 約数の数(少ない) $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種類以下参考
  個数切り詰めて使う場面がありそう
• 二項係数を全部足すと$2^n$、奇数番目or偶数番目だけなら$2^{n-1}$
• 写像十二相は考えるよりカンペを見た方が早い
• 二部グラフであるもの: 木、矩形グリッド(三次元でも)
  • ハニカムグリッドは二部グラフではない
  • 「立方体グラフ」はグラフ理論の用語で、現実の立方体とはちょっと違う
• 「○○の定理」の類
  • ピックの定理
  • ポリアの定理 混乱している様
• 達成するまでにかかる回数の期待値 $=$ 1回以上かかる確率 $+$ 2回以上かかる確率 $+$ ...

高度典型

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

• 畳み込み ABC392G
  形式的べき級数の考え方と相性が良い
• フロー
  • 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をやる
  • ただ殴れる
    • Aho-CorasickABC362G ABC268Ex
• 最小シュタイナー木問題 出所はだいたいこれ ABC364G ABC395G
• 並列二分探索 ABC394G ABC233G

軽めの典型問題

で悩まないようにしたい

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

その他

• 乱択 心の片隅に置いておく
• インタラクティブ