Algorithm

P, NP, NP完全, NP困難

NP完全とNP困難の違いがわかってない自分をようやく卒業できました。 ソースはWikipedia。適当にまとめるので、詳しく知りたい人は自分でWikipediaの記事見てください。 NP問題 まず、一番わかってないといけないのが、NPとは何かということで NP≠Non-Polyno…

サポートベクターマシンの勉強をする前に

サポートベクターマシンの理論をちゃんと勉強しようと思うと、マージン最大化やらカーネルトリックやらで、何で出てきたのかわからない数式がいっぱいで挫折する・・・という人は、ベクトルの勉強をするといいことがわかりました。ベクトルって言ってもベク…

PKU1273 Drainage Ditches

最大流量、最大フロー、Max Flow、Muximum Flow の問題。 USACO出展。

PKU1258 Agri-Net

最小全域木、Minimum Spanning Tree、MST の問題。隣接行列だけど。 USACO出展。

東大のアルゴリズムとデータ構造

http://hagi.is.s.u-tokyo.ac.jp/ade/ 「C言語入門」の正しい受講の仕方2 (特にプログラム未経験者)•「週に90分の講義を受けてるだけではプログラムは書ける様にはならない」ということを肝に銘じること(習うより慣れろ). 大きな差を感じる・・・。 こ…

diffが意外にむずいことが判明

学校で自前でdiffを作れって課題が出た。 余裕だと思ってたら、ただのEditDistanceだと出力が一致しない。 おんなじ操作を連続してやるときのコストは1っぽい。 これはがんばって実装せねば。

両側A*探索

両側A*探索のときにどういうヒューリスティクス関数を使えば解が正しいと保証されるのかということで研究室で奮闘中。 vを現在見ているノードとして s->tで片側探索するのときのヒューリスティクス関数をhf(v) t->sで片側探索するのときのヒューリスティクス…

パラメトリックサーチに変わる名前募集!!

パラメトリックサーチ - 前原の日記 でようやく正しいパラメトリックサーチというものがわかった。 (議論の元はココ-> SRM380 - にゃあさんの戯言日記) 今まで、解を想定してそれが条件を満たすかどうかをバイナリサーチで求めるという手法を、なんかほんと…

好きなアルゴリズム

あなたが一番好きなアルゴリズムを教えてください。 また、その.. - 人力検索はてな というのがなんか今やたらとブックマークを集めているようなので、自分もブログ内で答えてみようと思う。 わざわざここで答えるのは、これを見たICPC陣にもぜひ答えていた…

範囲更新データ構造(改良版)

この前のは同じ色が連続してしまう可能性があったが、ちょっと考えれば防げるんじゃないかと思ってコードを書き直してみた。これでconnectがいらなくなった。"upper_bound(x)"は「xより上」のxに最も近い値を指すイテレータを返すので、"--upper_bound(x)"が…

範囲更新データ構造

色塗り問題を解くデータ構造を勉強してみた。 Makegumiライブラリを参考にさせていただいて、何やっているか理解し、改めて自分で書いてみた。Makegumiには合宿3日目の最大流のときから本当にお世話になっている。 fromの情報だけあればtoの情報が要らなくな…

二部グラフの最大マッチング=最小頂点被覆

nyaasanに教えてもらった「最大流-最小カット定理」を使うということを元に、昨日わからなかった二部グラフにおいて最大マッチングが最小頂点被覆と等しいということを証明してみようと思う。 正直これを聞いても自分の中で納得するまでに大分時間かかってし…

最大マッチングと最小頂点被覆

二部グラフにおいて最大マッチングと最小頂点被覆は等しいらしい。 実際にいくつかの例で試してみたら確かにそうなるから正しいんだろう。でも理由がわからない。 そもそもこの事実は二部グラフ以外でも成り立つのだろうか。 誰か教えてください。まじめに。

二部グラフの最大マッチング

考察タイム終わった後実際に簡単な4問は解いてみた。 PKU2060で初めて最大流量を使わない2部グラフの最大マッチングのコードを書いた。Web上にメモっとこ。 typedef vector<vector<int> > graph; struct BGM { int L, R; //左右のノード数 graph g; vector<int> r2l; //右->左</int></vector<int>…

TopCoderはアルゴリズムのいい勉強

ICPC関係の人の間でTopCoderがはやっているみたいなのでちょっと興味を持った。いろいろTopCoderのサイトを見てみたので使えるページをメモっておこうと思う。 まず、参加するためには欠かせないコンテストスケジュール。 http://www.topcoder.com/tc?module…

二分探索

ちょっと二分探索の挙動で気になったことがあったので書いておく。挙動というのは指定した値が見つからなかった時や同じ値が複数存在した時にどうなるかということだ。配列内を探索するならSTLのlower_boundとupper_boundを使えばいいだけの話なのだが、最近…