ferinの競プロ帳

競プロについてのメモ

考察パターン

問題を見直していて使うと思った考察パターン、知識のメモ
後ろの括弧には白文字で使ったと思った問題などが書いてあります。

グラフや木

  • 頂点に値をもたせて葉から決めていく(DFSや木DP)(AGC010-C,ARC063-E,ARC083-E)
  • 仮想頂点を追加する(ARC029-C,JOI ゾンビ島)
  • 頂点条件を辺条件に言い換える(ARC029-C)
  • 奇数長のサイクルの有無が関わる→二部グラフ (AGC011-C,codefes2017qualB-C)
  • 森の連結成分数 = 頂点数 - 辺数 (AGC015-C)
  • 各頂点を根として木DPをN回やるとO(N^2) → 全方位木DP(ARC028-C,双子コン#4-D,NJPC2017-E)
  • サイクル内は自由に遷移できる→SCCやBCC(ARC030-C,AOJ2712)
  • 条件が追加されてる最短経路→拡張dijkstra(ARC061-E,AOJ2447,AOJ2585,AOJ1318,AOJ2425)
  • 集合を2分割→カット(ARC085-E)
  • 最短路に関わる辺しか使わない→最短路DAG(ARC090-E,RUPC2018 day3 F)
  • 色々条件が増えたMST → MSTから辺の交換で別の全域木を作る 参考(ARC093-E, AOJ 2536,AOJ1350)
  • 直径→中心,double-sweep (AGC001-C)
  • 完全二部マッチングの個数の偶奇 = 隣接行列の行列式の偶奇(ARC054-C)
  • 木の2点間距離 → LCA(ABC014-D,NJPC2017 H-白黒ツリー)
  • BITを使うとLCAに木の辺のコストを変更する処理に対応できる 蟻本p295 (NJPC2017 H-白黒ツリー)

データ構造

  • K-th number→BIT上二分探索 or 平衡二分探索木(ARC033-C,AOJ0343)
  • セグ木 → 更新:加算,更新,xor クエリ:和,最大,最小,最大最小の個数 など色々できる(RUPC2018day2-J,RUPC2018 day3 E)

DP

  • 2つの操作から選ぶ → DPに落とす(ex ナップザック) (AGC009-C)
  • DPテーブルを書くと更新が定数個 → インラインDP(AGC009-C)
  • 素数や要素のmaxが小さい→DPテーブルが持ちやすい

構築

  • 少ない要素数ででかい数をつくる → 2べきで指数爆発(ARC103-D)
  • 2次元グリッド→ヘビ 参考(AGC004-C)
  • グラフや木→ウニやパスの組み合わせ(AGC005-C,ARC103-E,SRM675 d1e)

数学

  • 二分累乗は行列や置換に適用できる (AGC006-C)
  • 確率的な形式を期待値を使って決定的な形式に変形する(AGC006-C, AGC007-C)
  • +1と*2を繰り返せばどんな数でもつくれる、+1と*2を別の操作に対応させて考える(AGC012-C,ABC077-D)
  • 2^k > 2^0 + 2^1 + … + 2^(k-1) (AGC022-C)
  • 順列の全通りについてスコアを足し上げる系→答えはスコアの期待値*N! (AGC023-C,AGC028-B)
  • 数式変形で前計算しておける形になる(ARC059-E)
  • 平均がKか?を考えるときは予めKを引いておくと区間の数を無視できる(ARC075-E)
  • 2^|A| = 集合Aの部分集合の個数 (ARC082-E)

文字列

  • 一致検索などはロリハ・z-algo・SAなどが強い(ARC055-C)

計算量

  • 部分集合の部分集合はO(4^N)ではなくO(3^N)になる (ARC056-C)
  • 調和級数O(logN) = 1/1 + 1/2 + … + 1/N (ARC068-E)

全般

  • 制約を強くする、自明なケースを場合分けで取り除いておく(AGC002-C,AGC008-C,AGC021-C,ARC068-E,AGC026-B)
  • まとめ方を変える(対称性,見る軸を変える)(確率系なら期待値の線形性,うまく排反になるようにまとめる) (AGC023-C,ARC055-C,AOJ2303)
  • 操作、要素が複数ある→独立、同一視、一つだけやってみる、何個か固定してみる(ARC077-E,ARC095-E,AOJ2200,AOJ2510,AGC012-C,ARC073-E,ARC098-E)
  • 操作順を変更する 入れ替える、逆順、削除→追加など(AGC014-C,cf#469 div2-D)
  • 操作の順序が実は関係ないので適当な順でできる(ARC079-E)
  • 不変量に注目 (SRM688 d1e)
  • 値が変化するタイミングに注目(AOJ2310,AOJ2298)
  • 別の形式の問題に帰着する 有名問題に帰着できたり答えが求めやすい形になったり
    • 区間グラフ(AGC017-C)
    • グラフ(AGC022-C)
    • Trie木(ARC087-E)
  • 差分を取ると見通しがよくなる(AGC006-C,AGC020-C)
  • 適当な順序でソートしておく(AGC018-C, codefes2017Final-D,AOJ2642)
  • 一部しか更新されない
    • 毎回一から計算するのは無駄(ARC035-C,並列二分探索)
    • 必要な場所だけ持つ 遅延評価,座圧 (ARC039-C)
  • 簡単な集合、列の組み合わせで表現(AGC024-C)
  • 制約からエスパー 半分全列挙,bitDPなど(AGC026-C,SRM696 d1e)
  • しなければならない操作を積み重ねていくと最適な操作になっている、蟻本p139(ARC040-C)
  • 貪欲によさそうな戦略 = 最適な戦略 なパターン(ARC094-E)
  • 偶奇性 操作しても偶奇が変わらない、偶数番目と奇数番目が同時に答えになることはないなど(AGC003-C,ARC092-E)
  • 補集合、補問題について考える(ex クリーク⇔安定集合) (ARC058-E,ARC090-E,ARC099-E)
  • K番目の値を求める → K番目の値がX以上か?の二分探索(ARC027-C,ARC107-D,JOI L番目のK番目の数)
  • 同じ操作を繰り返す→ダブリング、二分累乗、周期性 (ARC060-E,AOJ2320 Infinity Maze)
  • 逆操作が可能→剰余群的にまとめられる(ARC071-E)
  • 適当な割り当てから交換等を繰り返すことでスコアを上げると最適になる(ARC073-E,AOJ2642)
  • インタラクティブ→少ない操作回数で判定→二分探索(ARC078-E)
  • i<j,A[i]<A[j]な数とかは転倒数の要領でBITで数えられる(ARC075-E)
  • 辞書順最小なら貪欲に取る(ARC069-E,ARC080-E)
  • 重複なしな部分列を数える→辞書順最小なものだけを数える 参考(ARC081-E)
  • 辞書順最小な復元→後ろからDP、前から復元(ARC081-E)
  • 隣接swap操作で条件を満たす列にする回数→転倒数に帰着 (ARC088-E)
  • マンハッタン距離→45度回転(ARC103-D)
  • 和集合→包除原理(ARC096-E,ARC102-E)
  • 独立に数えられる(ARC110-D,AGC025-B)
  • 弾性衝突→入れ替わる(AGC013-C)
  • rangefreq → セグ木でO(log^2N) 蟻本p170(JAGsummer2018day3-D)
  • 区間が与えられる → 終点でソート (ABC106-D, TDPC-K, codefes2017Final-D,AOJ1246,SRM681 d1e,AOJ1347)
  • 2種類の要素からなる列(ex 括弧列)を+1/-1などに置き換え (JAGsummer2018day2-J)
  • 括弧列の分割→+1/-1の標高図で同じ高さのところをまとめる(cf#469 div2-C)
  • 誤差が大変な場合はmodを取った有理数を考える(JAGsummer2018day2-F)
  • 和と差で書かれた式 → 畳み込みに帰着してFFT(JAGsummer2018day2-E)
  • a[1]*x[1] + a[2]*x[2] + … + a[n]*x[n] は gcd(a[i]) の倍数になる ベズーの等式(cf#499 div2-E)
  • bit演算→2進数にしてbitごとに考える(codefes2016final-C)
  • 2次元グリッドの(x,y)に点がある → グラフでxとyに対応する頂点を結ぶ(cf#500 div2-D, marukaite)
  • 操作の答えに対する影響やi→j, j→iと操作する場合のコストの差を考える(AOJ2236,cf#212 div2-C)
  • 時刻iで状態を満たしている要素の集合・数を持ちつつ走査(=平面走査) (ARC077-E)
  • 構文解析BNFをい つ も の(再帰降下型構文解析)で処理できるように書き換える (AOJ2596)
  • 条件を満たす数の個数を求める → 桁DP, 10進数だけじゃなくて2進数とかに適用することもある(AOJ0570,yuki685,RUPC2018 day1 F)
  • 2次元平面→偏角ソートするとうまくいく場合(AOJ2310,ABC033-D,CSA#68-C)
  • 円上の要素を最短距離で取得する→引き返すのは高々1回 (ARC096-D)
  • O(変数の取りうる値^数式の変数の数) から O(変数の取りうる値数式の変数の数-1) (AOJ1248)
  • Kの倍数について考える → mod K で考える (AOJ2182,ABC077-D,みんプロ本選2017-C)
  • あみだくじは置換(RUPC2018 day2 F)
  • multi_setの同型判定→乱数rを使ってhash=(a[1]+r)(a[2]+r)…(a[n]+r) % modでできる (RUPC day1 C)
  • ゲームなら実験してgrundy数などを求める (yuki669,ARC091-F)
  • 区間の数に注目すると多すぎる→要素が何回出てくるかに注目(AGC028-B,SRM730 d2M)
  • 攪乱順列の種類数はモンモール数 (ARC009-C,SRM717 d2Hd1M)
  • 最大値の最小化→二分探索 (SRM676 d1E,SRM657 d1E)

ToDo: 全般のカテゴリ分けをちゃんとやる、新しいものの追加