インターンやら何やらで何もやる時間がなかったのですが、帰ってきたので少し書きます(また明後日から二週間何もできない)。文字列検索には主にローリングハッシュというものと、SuffixArrayというものがあるそうです。へぇ。 あるn文字のstring Sからm文字…

もはや蟻本ではないけど、アルゴリズム関係は全部蟻本カテゴリーに入れてしまおう。ゲーム木探索をするときの基本的な方法についてまとめてみる。 minimax法 自分は評価関数が最大になる手を打ち、相手はこちらの評価関数が最小になるように手を打つ。negama…

辺eにはコストd(e)と容量c(e)が定まっていて、sからtへ流量Fのフローを流したときの全ての辺の流量×コストの和が最小になる時の費用を求める問題。これは単純で、最大流のときとほぼ同じです。残余グラフを考えて、そこでコストを考慮して最短路に沿って流せ…

試験が残り一つなので適当に蟻本を読んでみることにした。 最大流 …グラフにおいてs(source)からt(sink)に水を流したときに最大どのくらい流せるか？蟻本にのっていたように、最初にdfsでsからtまで限界まで水を流す。 その後、水を押し戻したりして最大にな…

今度は最小全域木問題に関してまとめてみます。まず、最小全域木問題を解くには2つの方法が知られています。1.プリム法 2.クラスカル法 1.プリム法これはダイクストラ法と似ていて、O(ElogV)のアルゴリズムです。 ある頂点群Vの部分集合であるXとXの補集合を…

ARC031のD問題解こうと思ったら二部グラフの最大流とか言われてうぇええんって感じなので、グラフについて調べつつ忘れないように書いていきます。最短経路問題には3種類の解法があります。 1. ベルマンフォード法 2. ダイクストラ法 3. ワーシャルフロイド…