アルゴリズムの簡単なまとめ

Latest Author KisaragiEffectiveKisaragiEffective /Date 2020-01-27 00:23:15 / Views 33546
9 (Favした一覧ページはユーザーページから)

アルゴリズムの簡単なまとめ

運営者が昔、メモ程度にどこかに書いてたものです。間違っている箇所がありましたら教えて下さい。
順次追加・修正中(ページごとに分けてもいいし、良いページができたら削除したい)
  • 計算手段
    • 再帰呼び出し
      • 自分自身の関数を呼び出すこと、forやwhileのループでもできることが、再帰呼び出しのほうが記述しやすいこともある。
      • 末尾再帰
        • return に再帰関数を呼び出すこと、return以外に再帰呼び出しがないこと
          注意としては再帰の結果をすぐにreturnすること(再帰の結果を更に演算したりなどはNGのはず）
          動き的には末尾の再帰のreturnをすると、それ以降returnの処理しかないような動き。
        • これをする理由は、（言語によってはしてくれない）末尾呼び出し最適化が働き、スタックを定数量しか消費しないようにしてくれる。
  • 数学的アルゴリズム
    • 最大公約数 (GCD)
    • 最小公倍数 (LCM)
      • lcm(a,b) = a*b / gcd(a,b) で求められる。滅多にないがlcm(a,b)はオーバーフローしないがa*bはオーバーフローする可能性がある場合はlcm(a,b) = a / gcd(a,b) * b とする
      • 全ての素因数の指数に対してmaxを取ることに該当する
    • 素数を求める(Prime Number)
      • 素数は2,3以外は　6n+1または6n-1の数である。これを知っていると下の2つのアルゴリズムで更に早く求められるかも知れない。 より一般に、ある数で剰余を取った場合のパターンを元に計算量を削減する手法は"Wheel"と呼ばれる。
      • 試し割り
        • 2～n-1までで余りが出るかどうか求めて、全てあまりが出れば素数(実は2～√nまでで良い）
        • 実装は楽
        • smooth numberを生成するのに使うことができる。
      • エラトステネスの篩
        • 素数表（1～nまでの各整数が素数かどうかを全て判定する）を作る。
        • たくさんの数を判定する場合はこちらが良い。
        • 1～nまでの全ての整数に対して約数の数を求めるなどと言った時も同様の考え方をすることができ、色々な問題に適応可能。
        • うまく実装すれば線形時間となる
      • 区間篩
        • 素数表（L～Rまでの各整数が素数かどうかを全て判定する）を作る。
        • まず$\sqrt R$までの素数を求めておき、その素数のみを用いてL～Rの区間のみの篩をする。
        • 制約に $R \leq 10^{12}, \;\; R-L \leq 10^6$ などというのを見かけたらこのテクニック（あるいはこの応用）が使える可能性がある。
    • 冪剰余
      • $a^N$ を計算し、kで割ったあまりを求める問題。　普通にaのN乗を計算するとオーバーフローしたり、多倍長計算が出来ても重い、あまりを一つの掛け算ごとに行ったりテクニックを使うとO(log N)で計算可能になる。
    • 数字根
      • ある数値を表す数字を全て足し、結果の数値の数字を全て足し、という操作を繰り返し、最終的に得られる一桁の数字のこと。
      • 実はあまりを場合分けするだけですぐに求められる。（Wikipediaの合同式による定義を参考）
    • フェルマーの小定理
    • フロイドの循環検出法
      • 任意の数列(あるいはfunctional graph)に出現する循環を検出するアルゴリズム
  • グラフ
    • 頂点と頂点同士をつないだ辺を持ったもの
    • 歩道・ウォーク (walk)
      • 頂点と辺が交互に現れる列であって、最初と最後は頂点で、辺の両端点は左右の頂点をつないでいるものをいう
      • 歩道が 閉じている (closed) とは、最初の頂点と最後の頂点が同じであることをいい、それを閉歩道という
      • "progression"とも呼ばれる
    • 小道・トレイル (trail)
      • 歩道のうち、同じ辺を2度以上通らないもの
      • オイラー路（オイラーグラフ）
        • 小道のうち、すべての辺をちょうど1回ずつ通るもの（一筆書き問題）
    • パス・道・路 (path)
      • 歩道のうち、同じ頂点を2度以上通らないもの。明らかに、パスは小道である
      • これを「単純パス (simple path)」と呼び、歩道または小道のことを単にパスと呼ぶ流儀もある
      • ハミルトン路
        • すべての頂点を1度ずつ通る路のこと
        • 与えられたグラフにハミルトン路が存在するかを判定する問題はNP完全である
    • 閉路・サイクル (cycle)
      • 閉歩道のうち、最初の頂点だけを最初と最後でちょうど2度通り、それ以外の頂点は2度以上通らないものをいう
      • ハミルトン閉路
        • すべての頂点を1度ずつ通る閉路のこと
      • 閉路グラフ
        • グラフ全体で1つの閉路（閉歩道）のみで構成されているグラフ
    • 無向グラフ
      • 辺に方向がないもの（どちら共に行ける）A->Bへも B->Aへも行ける
      • 木
        • 閉路を含まない連結なグラフ。辺の数 = 頂点の数-1。
        • 二分木
        • 全域木
          • すべての頂点が連結である（孤立がない）木のこと
          • 最小全域木(MST:Minimun Spanning Tree)問題
            • すべての頂点が連結である（孤立がない）木にするための最小限のコストの辺だけ残したもの。
            • （それぞれの道路にコストが有り、n個の村があってすべての村をつなげるために、最小限のコストの道だけ作る問題）
            • 無向グラフに対する最小全域木は貪欲法（プリム、クラスカル）で解けるが、有向グラフに関する最小全域木は簡単ではない。（始点を除いて、入ってくる枝の中でコスト最小のものだけを考え、閉路ができなければ終了、閉路ができたらその閉路を1つのノードにしてグラフを再構成するというのを繰り返すと有向グラフに対する最小全域木を求めることができる）
          • 与えられた無向グラフに含まれる全域木の数は行列式を用いて数え上げることができる (Kirchhoff's theorem)
      • 二重辺連結成分分解
      • 二重頂点連結成分分解
      • 平面グラフ (planar graph)
        • 辺同士が交差することなく平面上に"描ける"グラフ
        • スパースである。つまり、$E \in O(V)$ (V = 頂点数, E = 辺の数)
        • 様々な問題が一般のグラフ上より高速に解ける。これには一般のグラフ上でNP-hardである問題も含まれる。
    • 有向グラフ
      • 辺に方向がないあるもの（行ける方向が決まっている一方通行） A->Bしかいけない　
        • もちろんすべての辺で B->Aの辺もある場合は、問題によっては無向グラフと同等になる。
      • DAG(directed acyclic graph)
        • 有向グラフで閉路（ループ）を持たないグラフ
      • functional graph
        • 各頂点点からちょうど1つの辺が出ているグラフ
      • 強連結(グラフ)
        • グラフが強連結であるとは、任意の2つの頂点$u$,$v$が「$u$から$v$」と「$v$から$u$」のどちらのpathも存在すること。
          • 強連結成分分解(Strongly Connected Component Decomposition)
            • グラフの強連結である部分グラフを検出し示すこと。
            • 検出した部分グラフを1つの頂点に置き換えること(縮約)をするとDAGになる。
    • 最大流、最小カット
      • Ford-Fulkerson's algorithm
        • 増加道に繰り返し流していく。強多項式時間アルゴリズムではない。
        • 動的な辺容量の変更に対応することもでき、容量が1の場合$O(E)$時間で更新できる。
      • Dinic's algorithm
        • $O(V^2 E)$。全ての辺容量が1の場合など、漸近的に高速なケースがある。
        • 一般的に高速だが最悪ケースを作るのは難しくないので過信できない
      • Push-Relabel
        • 実装によって$O(V^3)$や$O(V^2 \sqrt{E})$など。
        • "実用上最も高速"と言われることもある。
        • Excess scalingを用いると$O(V E + V^2 \log U)$。
    • 最小費用流
      • コスト最小二部マッチングでグラフが密な場合は問答無用でハンガリアン法を使いましょう。
      • 任意の最小費用流問題は辺容量が無限大であるネットワークに変換することができる
      • Successive Shortest Paths
        • 最短路を求めるアルゴリズムが色々考えられて難しい。一般的なグラフの場合は1回ベルマンフォードしてからポテンシャルを考慮したダイクストラをする
        • 枝のコストが非負なら最初からダイクストラで高速。グラフが万が一DAGなんてときはDP一択。
        • 単純な実装では多項式時間アルゴリズムでない。Capacity scalingによって多項式時間にできる。
      • Push-Relabel, Cost scaling
      • Cycle canceling
      • Network simplex
    • 有名な問題
      • 巡回セールスマン問題(TSP)
        • 辺にコストが有り、すべての頂点を１回だけ通り、始点に帰ってくる経路（つまり閉路）の最短経路問題
          • 辺のコストが1または無限大（通れない）の条件がつくとハミルトン閉路
          • NP困難
          • DPで$O(2^n n^2)$時間
      • 中国人郵便配達問題
        • すべての辺を１回以上通る閉路の最短経路問題
          • 一般グラフの重み付き最大マッチング問題に還元することにより多項式時間で解くことができる
        • 有向グラフの場合、最小費用流へ還元することができる。
  • データ構造
    • 連想配列・HashMap
      • 実装によっては衝突攻撃に弱く、特別な入力に対してTLEしてしまうことがある。
    • スタック(Stack)
      • push（値を最後に入れる）/pop(最後の値を取り出して消す）の操作ができるデータ構造
      • いわゆるLIFO(Last In First out)
      • 実装では、普通のリストを利用することもできるが、専用のクラスがある言語もある。
    • キュー(Queue)
      • queue (最後に値を入れる)/dequeue(最初の値を取り出す）の操作ができるデータ構造
      • いわゆるFIFO (First in First Out)　
      • 実装では、普通のリストを利用することもできるが、専用のクラスがある言語もある。
    • プライオリティキュー（優先度付きキュー）
        • 優先度を指定して、その順に取り出すことができる。
        • 一般的にプライオリティキューとなっているものは、dequeue時に$O(\log n)$で取り出せる。
        • Meldable heap
          • ヒープを融合(meld)する操作のできるヒープ
        • 二分ヒープ (binary heap)
        • pairing heap
        • leftist heap
        • fibonacci heap
    • Segment Tree
      • 区分ごとの値が計算可能な問題に対して（最小値/RMQ(Range Minimum Query)など）
        区分ごとの計算を予めしておき、データ構造として保持する。
      • 値を更新するのは$O(\log n)$
        値を取得するのは$O(\log n)$
        で可能
        • ちなみに配列での純粋な実装の場合は、値を更新するのは$O(1)$　値を取得するのは$O(n)$
      • 区間に対する演算を行い、区間に対するクエリを求める必要がある場合は、遅延伝播をすることで両方とも $O(\log n)$ で行える
      • 区間が広い場合は、クエリを先読みして座標圧縮すると良い
      • 区間が広い、かつ、先読みも禁止されている場合（オンラインアルゴリズムが求められている場合）、初期値が一定でクエリが少ない場合は、必要なノードをそのたびに動的に作ることもで解決できることがある。ただしメモリ使用量は増える。
      • 更新しなくて良い場合は、スパーステーブルなどを用いたほうが高速（ただし一般にはメモリはたくさん必要となる）
    • BIT、別名Fenwick Tree
      • Segment Treeの応用
      • 1〜n の範囲に対しての計算ができる場合にデータ構造として保持する。
      • 例えば　ak~anの部分和のような問題によい。　sum(k,n)=S(n)-S(k)なので　Sを効率的に求める
      • 計算量的にはSegment Treeと同じだが、（ビットテクニックを知ってれば）実装はこちらのほうが楽（更にSegment Treeより1.5～2倍程度速いので想定解法でなくても通るかも）
    • 平衡二分探索木
      • Randomized Binary Search Tree
      • Treap
      • 赤黒木 (Red-black tree)
    • Link-cut Tree
    • 永続データ構造
    • 平方分割
      • 複雑なデータ構造を実装しなくても、データをいくつかのまとまり（通常 $\sqrt{n}$ ぐらいずつ）にわけて保持することで色々な操作が $O(\sqrt{n})$ でできるようになることも。
      • クエリの平方分割
      • 平方分割によるRectilinear TSPの近似による2次元クエリの高速化
  • 場合の数
    • 場合の数は大きくなることが多いので ${\rm mod}\ m$ で答え求めることが多い。$(a \pm b)\ {\rm mod}\ m = (a\ {\rm mod}\ m) \pm (b\ {\rm mod}\ m)$ や $(a \times b)\ {\rm mod}\ m = (a\ {\rm mod}\ m) \times (b\ {\rm mod}\ m)$ が成り立つことを忘れないように。また、$(a / b)\ {\rm mod}\ m = (a\ {\rm mod}\ m) / (b\ {\rm mod}\ m)$ は通常成り立たないことには注意！（どうしてもなら、特に $m$ が素数なら逆元を用いることで割り算もできる）
    • 包除原理
      • 全体の数から、該当しない（重複している）数を取り除く原理である。
        具体的には $|A \cup B| = |A| + |B|- |A \cap B|$ のような集合の公式を用いて数え上げること
      • 詳しくはwikipediaなどを参照のことだが、競技プログラミングにおいて筆者は $\displaystyle |\bigcap_{S \in A} \overline{S}| = |\overline{\bigcup_{S \in A} S}| = \sum_{B \subseteq A} (-1)^{|B|} |\bigcap_{S \in B} S|$ という式の形で考えることが多い。
        つまり、$|S|$個の禁止事項があるときに全ての禁止事項を避けるような場合の数を求めたい場合、 禁止事項の部分集合に違反する(部分集合に入らない事項に関しては全く気にしない)ような場合の数を求めることができれば、元の問題の場合の数を求めることができる。
      • また、上式でいう$|\bigcap_{S \in B} S|$が$B$の要素数のみによって決まる場合などに(たとえば$f(n)$が$|B| = n$のときの値だとすると)、 $\displaystyle = \sum_{n=0}^{|A|} (-1)^n \binom{|A|}{n} f(n)$ といった形で使われることも多い。
        一般的な包除原理は時間計算量が指数なのに対し、この場合は多項式時間で求めることができるので重要である。
        また、上の条件を満たさない場合でもDPなどを利用することで多項式時間で包除原理をする問題もある。
      • 例：1～bの整数のうち、cでもdでも割り切れないものの数を数えよ
        • 「cで割り切れる」「dで割り切れる」ことを避けなければならない禁止事項であると考える
        • まず、どの禁止事項も気にしない集合とは、1～bの全ての数の集合であり、その要素数はちょうど b である
        • 次に、ちょうど1つに違反する場合とは、つまりそれぞれcで割り切れる場合とdで割り切れる場合である
        • 最後に、2つ全てに違反する場合とは、cでもdでも割り切れる場合のことである
        • 今回はc,dの2つであったが、これをk個に一般化することも簡単であり、$O(2^k k \log b)$程度の計算量で解くことができる
    • 順序が関係ある。n個からk個取り出す組み合わせは nPk
    • 順序が関係ない。n個からk個取り出す組み合わせは nCk
    • 順序が関係ある。n個から全て取り出す組み合わせは n!
    • パスカルの三角形
      • いわゆるコンビネーション　nCk　を計算するときに (n+1)段目の(k+1)番目の値である。
      • 二項定理などにも使える。
    • 中国人剰余定理 (CRT, Chinese Remainder Theorem)
      • 線形合同方程式($x \equiv a_i \pmod {m_i}$)が与えられたとき、$x$を求める。
      • 例えば、答えを${\rm mod}\ {p q}$で求めたい場合、$\gcd(p,q) = 1$なら${\rm mod}\ p$と${\rm mod}\ q$でそれぞれ答えを求めてからCRTをすることで求められる。
  • 計算量削減・枝刈り
    • メモ化・メモ化再帰
      • 過去に行った計算を保存しておき、一度した計算を行わないようにして計算量を削減する。
      • 「メモ化再帰」は、メモ化と再帰呼び出しを組み合わせたもの、TopCoder的には再帰する場合はメモ化再帰をよく使う。
    • 動的計画法
      • 漸化式的に問題を解く。　（どのサイトも難しい説明をしてるけど、要はこういうこと
      • （ただし、難しい説明がたくさんあるぐらいには色々な見方ができるのが動的計画法なのである）
      • わかってくると「メモ化再帰」と「評価順序が逆」で同等とのことをしているという見方ができる
      • さらにわかってくると、DAGのグラフにて値を更新しながら探索をしているだけという見方ができる。（DAGつまり閉路がないため、ある頂点$v$へ辺の探索で評価値最大を求めれば、その$v$の評価値はそれ以上更新されることはない）
  • 検索
  • 最小コスト経路
    • ダイクストラ法
      • 指定した２点間の最小経路コスト計算アルゴリズム。
      • 負辺には対応していない
    • ワーシャル-フロイド法
      • 任意のノード間の最小経路コスト(全点対最短路)計算アルゴリズム
    • ベルマンフォード
      • 負辺がある場合や、負閉路の検出に使うことができる（ワーシャルフロイドでもできるがワーシャルフロイドでは遅い場合に）
      • $O(V E)$
      • queue-based Bellmanford
        • キューを用いたベルマンフォード法の実装。
        • SPFA(Shortest Path Faster Algorithm)とも呼ばれる。
    • 動的計画法
      • DAGの場合は動的計画法が高速。DAGでなければ難しい（実際には体力は常に減っていく所持金は常に減っていくなどの関係があればDAGになるのでDAGになることも多い）
      • 部分和問題
      • ナップサック問題
  • 累積和手法（いもす法）
  • ゲーム
    • Nim
      • 複数の山があり、それぞれの山には何個か物がある、同じ山からなら１個以上物が取れる、最後の１個をとった人が勝つゲーム
      • 簡単に計算できる必勝法が存在し、ある問題がNimに帰着できると簡単に答えが出せる。
      • 最後の一個をとった人が負けになるパターン（逆型）もあるが、簡単に答えは出せないらしい。
    • Grundy数
      • 2人で交互に行動し、行動できなくなったら負けというタイプのゲームに定義される量。
  • 幾何
    • 点の多角形に対する内外判定
      • http://www.nttpc.co.jp/company/r_and_d/technology/number_algorithm.html
      • なお、点から半直線を引いて何回交わるかというのは、多角形の線分の上をべたーっと通るとまずい（あるいは面倒な）ので、ランダムな方向に引くか、最初に図形をランダムな角度だけ回転しておくと良い（最初にランダムな角度回転する手法は、$x$ 座標が全て等しいケースがコーナーケースになるなどという場合にも回避できるので競技プログラミングでは汎用的に使えるコーナーケース回避策）
      • Arccosを使う方法は、遅く、問題によっては普通にTLEになる。また、誤差の蓄積も激しく、0かどうかの判定は絶対値が $\pi$ 以下かどうかとしたほうが良いぐらいに激しい（閾値を0.1にするなどではぬるい、EPSなんてもってのほか！）。