好きなアルゴリズム

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


で、一番好きなアルゴリズムだが、

Adaptive Mesh Refinement

にしたい。こういう風に幾何問題を分割統治で解いてるのをはじめてみたとき感動した。本当は好きなのはAdaptive Meshに限らないので「幾何問題を分割統治法で近似的に解く手法」でいい。それでも、"Adaptive Mesh Refinement"にしたのは名前がかっこいいからw

確かはじめて分割統治で解いているのを見たのは404 Not Found
2004年11月号 点の密集区域(石畑 清)PDF:370KB
の最後に書かれてる解法だ。

ま、ここで幾何アルゴリズムを答えてしまうところがICPC日本サイトの幾何問題の多さに毒されてる気がするけど。


ただ、リンク元を見た限りあまりみんなが知らないようなのをあげてもあまり支持を受けてないみたいだったので、もっと一般的なのからあげると、単純に二分探索が好きかもしれない。

やっぱり、ソート済みなものの問い合わせをO(logN)でできるのはすばらしい。
一度習ってしまえば当たり前だけど、意外に気づかない気がする。

ちょっと応用になってしまうけど、スタンフォードローカルコンテストの問題 - awakia-nの日記で書いたようなパラメトリックサーチとか言われるものなんてほんとに気づかなかった。

実世界でも、デバックのときにコメントアウトする場所とかは微妙に二分探索応用できる気がするし、シンプルだけど何かと応用の利くアルゴリズムな気がする。