blogskol

思わず声に出して読みたくなるブログ

志望分野に向けて現在まで勉強してきたことの概要を 3~5 ページ程度にまとめてください。

17日金曜日の17時までにタイトルのそれをやらないといけないんですね
あとこれまで学んだ中で気に入った数理科学系の理論か定理を適当に一つ2~3ページのレポートに書いた上で英語で10行程度の要約も必要らしくて厳しい
そんなわけで取り敢えず勉強してきたことの概要の方を今書いてるやつそのまま晒すので、怪しいところを教えてあげて
//は提出には書かないコメントね
あと普通にあとこだ黄色が今持ってる知識をドーンってしてるからもしかしたら何かしら参考になる人がいるかも?(いるかなぁ)


ここから提出予定内容

志望分野に向けて現在まで勉強してきたことの概要

学んだアルゴリズムやデータ構造を中心に書く。グラフでは頂点数をN、辺数をMとする。
四則演算や比較はO(1)で行えるものとする。(従って、擬多項式時間のものも多項式時間のように表記する)

木関連

クラスカル法、ヤニークプリム法

最小全域木を求めるアルゴリズム最小全域木が存在する(=連結である)グラフに対して最小全域木をO(MlogN)で求めることが出来る。二つは多少違うがどちらも辺の選択をそれぞれの選択規則の元で貪欲に行う。

木の直径

木の最も遠い二点を求めるアルゴリズム。適当な一点からDFSやBFSを用いて最も遠い点uを求めたのち、uから最も遠い点vを同様に求めるO(N)の個人的にかなり非自明なアルゴリズム

木DP

根を一つ固定した木について、自分の部分木の計算結果をメモすることで葉から再帰的に各頂点を根とした部分木に関する特定の値を高速で求めるアルゴリズム。演算はモノイドが載せられて、二項演算をO(1)とした時O(N)で全体が求められる。

全方位木DP

木の各頂点vについて、vを根として木DPを行った時のvを頂点とする部分木の値を求めるアルゴリズム。素直に各頂点について木DPを行うとO(N^2)かかるが、他の頂点を根として計算した時の値を適切に再利用することでO(N)で求められる。

木以外のグラフ関連

ダイクストラ

単一始点最短路問題(辺に重みのついたグラフが与えられた時始点sから他の各頂点への最短経路)を求めるアルゴリズム。最短経路を求めていない頂点の中で最もsからの距離が短い頂点の最短路を決定することを繰り返すことでO(N^2)やO(MlogN)で求められる。辺の重みは全て非負の必要がある。

ベルマンフォード法

ダイクストラと同様に最短経路を求めるアルゴリズム。辺の重みにも制約はない。頂点vまでの最短経路はある頂点wまでの最短経路と辺wvのコストの和で表せることを利用し、値が更新出来るところが存在しなくなるまでループを繰り返すことでO(NM)で求めることが出来る。ループ回数を記録することでコストの総和が負の閉路の存在の検出も出来る。

ワーシャルフロイド法

全点対最短路問題(辺に重みのついたグラフが与えられた時任意の二点間の最短経路)を求めるアルゴリズム。ベルマンフォード法を全ての二点間で行うような感じで、O(N^3)で求めることが出来る。

フロー関連

Ford-Fulkerson法

最大流(各辺に流せる容量が与えられたグラフ上で始点から終点まで水をどれだけ流せるか)を求めるアルゴリズム。一度流したところをキャンセルすることを念頭に置きながら流量が増える道をDFSで見つけるたびに貪欲で流す。最大流量をFとして最悪計算量はO(FM)だが実際はもっと早く終わることが多い。証明には始点と終点を分ける最小カットを用いる。

二部マッチング

二部グラフの最大マッチングを求めるアルゴリズム。始点と終点の頂点をグラフに追加してから前述の最大流を行えばよい。

最小費用流

各辺に流せる容量だけでなく、単位流量あたりのコスト(費用)も設定されたグラフで、始点から終点まで流量Fを流すのにかかる最小費用を求める問題。最大流と同じように一度流したところをキャンセルすることを念頭に置きながら、現時点での最も単位流量あたりのコストの小さい道を見つけるたびに流せるだけ流すことを繰り返す。負辺を含むグラフでの最短路を見つける必要があるためベルマンフォード法を使う。

燃やす埋める問題

複数の小問題があり、問題ごとに選択肢が存在し、選択肢同士にも依存関係があるような問題で費用の最小化などを目指す問題。呼称はおそらく競技プログラミング特有のもの。小問を点、選択肢とその利益を辺に見立てた、カットと各小問に対する選択が一対一対応する有向グラフを作り最小カット(=最大フロー)を用いて解く。

データ構造

プライオリティーキュー(二分ヒープ)

データに対して最小値の取得、要素の追加、最小値の削除を行うデータ構造。データを「子の要素が親の要素以上」と言う制約を満たす二分木で管理する。要素数Nに対して、最小値の取得をO(1)、要素の追加と最小値の削除をO(logN)で行える。空間計算量はO(N)。

二分探索木

データに対して特定の要素の存在判定、追加、削除を行うデータ構造。データを「左の子とその子孫の要素は全て自身以下、右の子とその子孫の要素は全て自身より大きい」と言う制約を満たす二分木で管理する。要素数Nに対して操作はそれぞれ最悪O(N)かかるが、二分木の高さをO(logN)に保つ平衡という操作を使うとO(logN)で全て行えるようになる。

セグメント木

数列に対して特定の区間クエリ(区間和や区間最小値など)と要素の変更を行うデータ構造。クエリの演算はモノイドを要求。データのクエリ結果を2のべき乗個ごとに記憶することで操作を数列の長さNに対してそれぞれO(logN)で行える。前計算と空間計算量はO(N)。

遅延伝播セグメント木

セグメント木を要素変更だけでなく区間変更もできるようにしたもの。区間変更と区間クエリに関していくつか制約がある。データのクエリ結果と同様に変更操作も2のべき乗ごとに記憶し、複数の変更操作をマージしたりすることでそれぞれの操作をO(logN)で行える。前計算と空間計算量はO(NlogN)。

永続セグメント木

セグメント木で要素変更する際、要素変更前の状態も記憶しておくもの。「直近3回の要素変更の前の状態での区間クエリ」とかに答えられる。要素変更時には現在のノードの値を更新せず新しいノードを作りそこに変更後の要素を入れるようにする。前計算はO(NlogN)、空間計算量は要素変更の回数をQとしてO(NlogN+QlogN)。

フェニック木

数列に対して特定の区間クエリと要素の変更を行うデータ構造。データのクエリ結果をセグメント木と同じように管理するが、[0,a)の形の区間クエリの際に必要ないノードを持たないことで前計算と空間計算量をO(N)に抑える。セグメント木に比べ実装が軽い。[0,a)の形の区間クエリにしか答えられないため、[a,b)のような区間のクエリは演算が逆元を持つ時のみ行える。演算が逆元を持たない場合は一点取得が出来ないため一点更新が出来ない。一点に対する演算による更新には演算の可換性を要求する。

Union Find木

グラフに対して辺の追加と任意の二頂点の連結性の判定を行うデータ構造。連結成分の個数やある頂点の連結成分の大きさなども持たせることができる。各要素を頂点とし、連結成分が同じ木に属するような根付き木の集合でデータを管理する。各要素は自身の連結成分を属する木の根によって判断し、その際に辺を適切に付け替えることで計算量を大きく落とす。操作は要素数をNとしてそれぞれならしでO(logN)よりも高速に行える。空間計算量はO(N)。

Convex-Hull Trick

f(x)=ax+bの形の直線の集合に対して、直線の追加と任意の実数tに対して集合のf(t)の最小値を求めることが出来るデータ構造。直線の集合に対して各値での最小値が凸形になることを利用し、xの区間ごとに最小値を取る直線を管理しておくことで高速化する。計算量は追加する直線の傾きや実数tに対して単調性があるかどうかで変化する。

文字列関連

MP法

与えられた文字列Sに対して、各iについて「Sの先頭i文字の接頭辞と接尾辞がi未満で最大何文字一致しているか」を求めるアルゴリズム。素直にやると文字列長Nに対してO(N^4)かかる。MP法ではiが小さい方から順に求めていくが、値の再利用を適切に行うとO(N)で行える。さらに高速化されたKMP法と言うのもあり、1ステップ数にかかる最悪時間が短くなる。

Manacher法

与えられた文字列Sに対して、各iについて「Sのi文字目を中心とする最長の回文の半径」を求めるアルゴリズム。素直にやると文字列長Nに対してO(N^2)かかる。i-2j文字目を中心とした時の結果とi-j文字目を中心とした時の結果を再利用することでO(N)で行える。

Z algorithm法

与えられた文字列Sに対して、各iについて「SとSのi文字目以降の接頭辞が何文字一致しているか」を求めるアルゴリズム。素直にやると文字列長Nに対してO(N^2)かかる。Manacherと同じような感じで、既に求めた結果を再利用することでO(N)で行える。

その他

ナップサック問題

重さと価値のあるいくつかの荷物を耐荷重の決められたナップサックに総価値を最大化して詰める問題。動的計画法を用いることで要素数N、対荷重W、総価値Vに対してO(NV)やO(NW)で求めることが出来る。ただし擬多項式アルゴリズムであり、ワードサイズを考慮に入れるとNP困難である。

高速フーリエ変換

離散フーリエ変換を高速で行うアルゴリズム。長さNの数列A,Bに対して、C_k=\sum_{i=0}^{k}A_i B_{k-i} を満たす長さ2Nの数列Cを求める(ただしA_0=B_0=0とする)。素直にやるとO(N^2)かかるが、数列を周期Nの波と見なして周波数の世界を一度経由することでO(NlogN)で行える。

Grundy

公平ゲーム、不偏ゲームなどと呼ばれるゲームでの初期盤面から適切に両者がプレイした際の勝者を判定するアルゴリズム。代表例はNim。各盤面にはGrundy数と呼ばれる数を、その盤面から一手でいける各盤面のGrundy数から割り当てる。この時盤面干渉しない複数のゲームが並行して行われている場合に、ゲームごとに独立に求めたGrundy数から最終的なゲームの勝敗を求めることが出来る。

単体法

線型計画問題を解く方法の一つ。線型計画問題に最適解が存在するなら必ず最適基底解があることに注目し、基底解を目的関数値が下がらないように見ていくことで最適基底解を求める方法。様々なピボット規則があるがどの規則に対しても、それぞれ指数時間かかる入力が発見されている。指数時間がかかる入力が存在しないような規則が存在するかは未解決問題。実際には多くのケースでは線型時間で解ける。最初に基底解が与えられていない場合は基底解を求める必要があり、変形した問題に単体法を用いる。

ダブリング

a^nのような、同一要素の演算(モノイド)を高速で行うアルゴリズム。a^(2^i)はi回で求められることを利用し、nを二進法でbitごとに考えることで答えをlog n回程度の演算で求める。

アルゴリズム以外

C++

プログラミング言語。上記のほとんどをライブラリなどで書いた。競技プログラミングで2000問以上解いた。

P、NP

問題の難しさに関する指標の一つ。Pは多項式時間で解ける問題の集合、NPは問題の解が多項式時間で正しいか判定出来るような問題の集合を表す。PならばNPであるが、逆が成り立つかは未解決問題(成り立たないと言うのが通説)。NPのどの問題よりも難しい問題をNP困難と言い、NPかつNP困難である問題をNP完全と言う。

双対定理

線型計画問題の主問題と双対問題の目的関数値に関する重要な定理。線型計画問題周りの様々な定理の証明に用いられる。二つの問題の実行可能領域での目的関数値は(最適解が存在するなら)ちょうど双方の最適解での値のみ一致する。

//説明が面倒臭いから書かないけどやったやつ:凸包とか最小包含円とかの幾何、最大長方形、二分探索三分探索、平方分割、12写像
 あとやり切ってないけどDEGwerさんの数え上げPDFとかEDPCとかも割と大きい なんで蟻本すら終わってないんだろうな