上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと　"ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー

プロコントークを更新しました。前・実行委員長へのインタビューを掲載しています。 (2009/11/19) 本日よりエントリーの受付を開始しました。プロコンに参加希望の方は、まずはお早めにエントリーをお願いします。なお、エントリーをいただいた方には、問題発表日の2009年11月26日(木)が近づきましたら、お知らせのメールをお送りします。 (2009/11/19)

X×Y個のセルから成るグリッド上のスタート地点から出発し、全５種類のパチクリ（生物）を捕まえた状態でゴール地点まで行く最短コストを求める問題です。各パチクリはそれぞれ、火、氷、木、土、水の属性を持ち、火のパチクリは氷のパチクリを捕まえることができ、氷のパチクリは木のパチクリを捕まえることができ、といったように火→氷→木→土→水→火というような属性の関連があります。スタート地点で最初に持つパチクリを１つ選ぶことができます。グリッドのサイズx, y はそれぞれ2以上1000以下で、各属性のパチクリの数はそれぞれ0以上1000以下です（全体の数は5000以下）。 最初に１つのパチクリを選んだ後のパチクリを捕まえる順番は、上記属性の関連の順番になります。例えば最初に火の属性をもつパチクリを持っていれば、氷、木、土、水の属性をもつパチクリを順番に捕まえてゴールに行けばよいので、下図に示すDAG（Di

ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ

ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ

あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。

こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日本語版の解説

Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの