アルゴリズムの構築法

編集履歴

アルゴリズム

概要

  • アルゴリズムを構築するアルゴリズムとして
    1. ランダムなアルゴリズムを考える
    2. 矛盾しないかを実験する。矛盾しなければ終了する。
    3. (1)に戻る。
  • を走らせているのがマズそう

精神論

気合

  • AtCoder 700点とかで考察が入り組んで更にバグると、方針が合っているかの自信をなくしてしまう。やり切る気力大事。

考察が間違っていることを認める

  • ある考察をやっていた時に行き詰まったら、次の手をちゃんと打つ
    • 配るDPではなくもらうDPにする
    • 始めの換言が不適切かもしれない

数学的帰納法的思考

  • プログラミングは全て数学的帰納法
  • [0, i)の転倒数がわかってるとするじゃん？からスタートすると一瞬で正しいアルゴリズムを演繹できる

考察テクニック

  • 考察を始める前にどういう戦略で行くかを考えたほうが良さそう。BFS木みたいなのを頭に描く。マラソンの考察みたいに。

考察を戻す

  • 初手の換言から見直す
  • ある考察を行ったと、以前詰まった考察に戻ると、解ける事がある

考察を網羅する

  • DPでは、状態を前から見るか後ろから見るか、配るか集めるかなどは、全部試せるはず。ちゃんと試す。
  • 構築でのスーパーパラメータをちゃんとふる
    • ARC 102 D - All Your Paths are Different Lengthsでは、2進数から3進数で考えて、その後2進数に戻れば解けた。他の道での考察が役立つことがあるので、諦めた考察の道に戻ることも大切。

モデル化を精緻に行う

  • 大小を明示した考察のモデル化
    • 割とりんごさんがやっている

ちゃんと数式を書く

  • 境界条件など割と適当にやりがちだが、ちゃんとやる
  • 考察距離が長いと、導出した定理的なものを使うのだが、それの境界条件が甘くなるとバグる。
  • 怪しい式変形は前後で正しいかをちゃんと確認
    • どこがバグっているかを後で調べるのがめちゃ大変なので
  • 数式で表現する方法を拡大するように精進する
    • s.t. の自動的な変形に慣れてなさすぎる。cntだったりminだったりを分解して錬成するの下手。stは明示して書いた方が良さそう。(ARC 100E)
    • 数え上げはkの数え上げを<kから錬成するし、逆も可能。maxは<のstを=から錬成可能
    • cnt_Q a = cnt a - cnt_{not Q} a
    • cnt_{i, j s.t. i+j = k} g(i) = cnt_{i, j s.t. i+j <= k} g(i) - cnt_{i, j s.t. i+j <= k-1} g(i)
    • max_{i, j s.t. i+j < K} g(i) = max_{k < K} max_{i, j s.t. i+j = k} g(i)

操作前後の不変量

  • 操作が何かを保存している場合、それが必要条件や高速になっているため重要な考察となっているケースが多い
  • ある量がmod kであう
    • ARC 94 mod 3であう
    • Code Festival 2016 Tournament 2A mod 2であう

必要条件と十分条件

  • 全くわからないタイプの問題には、しばしば、必要条件を列挙していたら実は必要十分条件だった、というタイプがある
    • 必要条件が足りない場合は、漏れているケースを実験的に探索する必要がある。
    • 必要条件や十分を列挙し、ダメなケースを実験的に探すと見えてくるパターンがある
  • 例
    • https://atcoder.jp/contests/arc094/tasks/arc094_d 操作がmod 3を変えないところまではわかる。f(s, t) = sからtに行ける、という関数には、もう少し条件が必要で、これを実験的に構成するとfがわかる。このfを数え上げ化することができるのでOK

状態の追加

貪欲

  • 制約上何らかの貪欲が動かないと絶対解けないだろみたいな雰囲気を出している問題で、貪欲法を探索する方法
  • 貪欲法は、反例を頑張ってあげようという気持ちになるほうがよい。反例を揚げられなければ、正しいアルゴリズムであることの説明にも行き着く。
  • 基本的に人間は列の操作順序なんぞを考えるほど良い脳みそを持っていないので、再帰的に考えなければならない

実験

  • 自明な必要条件を除いて、全探索してみる
  • 実験時、例えば辞書順最小の数列を出すなど、制約をつけると見えてくる場合がある

問題から典型的思考へ

数え上げ

  • 「初期状態Sが与えられる。操作Xを0回以上繰り返した時、到達可能な状態Tを数え上げよ」
    • f(S, T)をSからTに到達可能か？という判定関数とする。これが高速に求まれば、DPなどに変換することができる
    • 700点のどれか

整数論

  • 素因数ごとに独立（素べきごとに独立）というのは非常に重要なアイディアになりえる
    • 整数はベクトル表記して、素因数ごとに独立だというスタートの切り方をしてもいいかもしれない
    • Codeforces Hello 2019 D

ゲーム

  • Aさんが最大化してBさんが最小化する
    • どちらかの最適戦略は決め打ちできるパターン(Code Festival Tournament 2B)
    • 貪欲に取れるパターン
    • ちゃんと考えるパターンとある。

最小化

  • 数列a, bがあって、sum (a_iもしくはb_i)を最大化するタイプ
    • 最小費用流
    • a-bをsortして貪欲
    • a_i -> b_iに辺を張ってグラフ問題に落とす（）

i != jなるものの数え上げ

  • 上から2つ考えるのは典型

中央値

  • 二分探索
  • 対称だと平均値に一致

ガソリン系

  • ゴールからやるのが典型
    • Code Festival 2018 Qual A - D

グラフ

探索的な考察

  • s_i, t_iをINFなり0なりで繋いじゃう
    • コスト0で繋ぐと「s_i, t_iを同一視する」という意味になる。

絶対に選ばれない辺・頂点を枝刈りしておく

  • 元のMSTで選ばれない辺は、操作しても依然として使われない Code Festival 2016 Tournament 1A

とりあえず辺を張ってみる

  • 頂点と頂点を結ぶクエリは、とりあえずそこに辺を張ってみるというのが多い

数学

  • ある程度の難易度になると、必要とされる数学も高度になってくる

総積

  • ∏i∈[0,n)ai∏i∈[0,n)bi=∏i∈[0,n)aibi\displaystyle \prod_{i \in [0, n)} a_i \prod_{i \in [0, n)} b_i = \prod_{i \in [0, n)} a_i b_i
  • 当たり前だけど

総和と総積の交換法則

  • nn本の数列DiD_iがある。DiD_iの添字集合は[1,∣Di∣][1, |D_i|]であるが、その部分集合IiI_iが予め定められている（IiI_iは定数であることが重要）。この時、

    • ∑v1∈I1⋯∑vn∈In∏1≤i≤nDi,vi=∏1≤i≤n∑vi∈IiDi,vi\displaystyle \sum_{v_1 \in I_1} \cdots \sum_{v_n \in I_n} \prod_{1 \le i \le n} D_{i, v_i} = \prod_{1 \le i \le n} \sum_{v_i \in I_i} D_{i, v_i}
    • 要するに因数分解に相当している

  • 長さ22の数列aaと、長さ33の数列bbがあって、

    • a1b1+a1b2+a1b3+a2b1+a2b2+a2b3=(a1+a2)(b1+b2+b3)a_1 b_1 + a_1 b_2 + a_1 b_3 + a_2 b_1 + a_2 b_2 + a_2 b_3 = (a_1 + a_2) (b_1 + b_2 + b_3)ということ。

  • これの凄いところは、nn個あった∑\sumが11個に抑えられるところ。

  • 例題

    • ARC 59 E
    • Codeforces Hello 2019 D

確率変数と期待値

  • 独立とは限らない確率変数X,YX, Yに対して、E[X+Y]=E[X]+E[Y]E[X+Y] = E[X] + E[Y]
  • 独立な確率変数X,YX, Yに対して、E[XY]=E[X]E[Y]E[XY] = E[X] E[Y]
    • Codeforces Hello 2019 D

包除原理

証明

  • 貪欲は証明まで含めて「解けた」と言える。

証明のパターン

  • 最適と示したい操作Aがある。操作Aの途中で、一箇所だけAでない操作に変えて残りは全部操作Aをすると損する
    • 操作からなる列を作るとき、あるステップで貪欲法が選んでくるものではないものを選んでそれ以外は貪欲法が選んでくるものを選ぶ、とすると解が悪くなる時は貪欲でないステップがあるものは最適解になり得ない
    • クラスカル法の証明
    • より一般にマトロイドの貪欲も同じ感じらしい
  • 2 つを swap すると得をしてその swap 関係が全順序になってる
  • 凸だから山が登れる

マッチングの貪欲

  • AtCoder Regular Contest 092 Cに多くが詰まっている。

(a)そもそも、使ってない頂点集合Sに対する操作「Sから頂点Aそのものを消す、もしくはSから頂点Aとそれに隣接する頂点Bを2点消してスコアを1あげる」を繰り返してスコアが最大となるものが最大マッチングだということがわかってなかった (b)‪最適に遷移可能な状態からなら、一番悪くならない操作をすれば、最適に遷移可能な状態を保持する‬ (0) どんな順序で頂点を見ても、最大マッチングを達成するような方法がある。最適に遷移可能な頂点集合Sがある。これから、任意の頂点Aについてある操作を行うと、最適に遷移可能な頂点集合になる。 これは、最大マッチングを一つ想定して、それを達成するような操作方法を考えれば明らか (1) 最適に遷移可能な頂点集合Sがある。これから、任意の隣接頂点を持つ頂点Aについて、ある頂点Bが存在して、A-Bを取り除いたS-ABは最適に遷移可能な頂点集合である。（俗っぽく言うと、取れるときには取らないと）これは隣接してるのにAだけ消すのは最適に遷移可能な頂点集合であるという性質を壊してしまう可能性があることから言える。 もう少し厳密な言い方をすると、「任意の最大マッチングに到達可能な頂点集合Sについて、任意のSに含まれる頂点Aを持ってきても、あるAを消す操作fが存在して、f(S)は最大マッチングに到達可能な頂点集合である。」 これは(0)の操作を限定している。 (2) (1)から、任意の時点でSから任意の頂点Aを選択しても、最適に遷移可能な頂点集合に遷移できる。いすれ頂点が0個になるので、自明にマッチングが0が最適となる状態にいつかたどり着く。（俗っぽく言うと、再帰的に） (3) (2)で任意の順序で頂点Aを選んでも良いと言ったが、頂点Aについて複数の隣接頂点があった場合、最適に遷移可能な頂点集合である性質保つように、頂点Bを選ぶ方策fは自明ではない。 (4) 方策fは、(1)から頂点Aについて必ず存在するので、頂点Bの選び方は今後の選び方の可能性を最大化するように選べば、最大マッチングに到達可能であるという性質を保持した操作になる。必ず最大マッチングに到達できる集合に遷移できる、ということが(1)でわかっているので、可能性を最大化できればそれが最大マッチングに到達できる経路の一つであることが言える。 (5) 方策fは、隣接頂点集合の包含関係からわかる場合がある。n(X)を頂点Xの隣接頂点集合とする。n(A)からどのBを選ぶべきかを考えると、for all B’ in n(n)-B. n(B) in n(B’) ならばよい。（これは最も可能性が低いやつを除外しようという話）

証明の練習問題

  • 証明の訓練をするしか無い

  • Topcoder SRM 697 D1E

  • ARC 53C

    • 上がって下がってする奴
    • あの貪欲の構成は面白かった気がする

  • AGC 03B

  • AGC29 B

    • 辺eをマッチングに使わないのならば、辺eを取ることでマッチング数を1あげることができる
    • 次数>1を使うとすると、次数>1を使う他のマッチングe=(次数>1, v)があるが、マッチングとして使えなくなる朝展が次数>1, 次数=1, vの三点となってしまい、真に悪くなる
    • 任意の頂点uについて、u-v とマッチするよりも良いマッチングの仕方があるとしたら、 a-u v-b みたいになってるはずで、対偶？を考えると、uがどれともマッチしない場合よりも何かとマッチしたほうが良い。
      • u-v とマッチするよりも良いマッチングの仕方Xがあるとします。Xにおいてuもvも使わないなら、u-v使ったほうがよいです。Xにおいて u使わない & v-b よりも u-v, bフリー のほうが良いです。Xにおいて v使わない & a-u のときも同じです。

種類を問う問題

  • 種類系は最後の場所を見とくのは典型
    • RGBSequence

DP

  • key-val交換は非常によく使う
    • 木DPでの利用例: AISing 2019 E

最終更新: 2020-01-01