ALGORITHM NOTE 難儀な人たちが座る椅子
面倒なシミュレーションの問題です。 A, B, C, D それぞれの国の人の座り方をシミュレートする関数、setLeft, setB, setC, setD を素直に作りました。 椅子の状態を保持する配列（ここでは配列C）の先頭と末尾に番兵として'X'などを入れておくと実装が楽になるかと思います。 setD で使う getDist(int p, int d) は、p 番目の椅子から d 方向 （正が右、負が左）への空席の数を返します。 問題原文にある、椅子のサイズは大きすぎると思うのですが・・・ミスプリントでしょうね（AOJでは修正されています）。 #include<iostream> using namespace std; #define rep(i,s,e) for ( int i = s; i <= e; i++ ) #define MAX 10000 #define INFTY
ALGORITHM NOTE 高校生一人旅 ~青春の片道切符編~
グラフの最短経路（コスト）を求める問題です。残念ながら典型的な問題です。 ワーシャルフロイドが想定解法なのかもしれませんが、 ダイクストラのアルゴリズムで解きました。 #include<cstdio> #include<queue> #include<algorithm> #define rep(i,b,e) for ( int i = b; i <= e; i++ ) using namespace std; #define MAX 1000 #define INFTY (1<<21) int n, C[MAX+1][MAX+1], T[MAX+1][MAX+1]; class State{ public: int p, e; State( int p = 0, int e = 0 ): p(p), e(e){} bool operator < ( const State &s ) co
ALGORITHM NOTE Verbal Arithmetic
Verbal Arithmetic バックトラックで解いてみました。 適当な枝刈りをすれば手元で１０秒くらいorz。 優れた解法はlaycurseさんのブログを参照。 #include<iostream> #include<string> using namespace std; #define MAX 12 int N, L[26], R[26], LT[26][10], RT[26][10]; string S[MAX]; int num[26]; bool used[10]; int cnt, MDL[26], MDR[26]; void setValue( string str, int a[] ){ for ( int i = str.size()-1, p = 1; i >= 0; i--, p *= 10 ){ a[str[i] - 'A'] += p; } } bool z
ALGORITHM NOTE Discrete Speed
Discrete Speed ダイクストラのD。 「現在の場所、前にいた場所、速度」のノードでグラフを作りました。 #include<iostream> #include<cstdio> #include<queue> #define rep(i, n) for ( int i = 0; i < n; i++ ) using namespace std; #define MAX 30 #define VMAX 30 #define INFTY (1 << 21) class State{ public: int pos, from, v; double cost; State( int pos=0, int from=0, int v=0, double cost=0): pos(pos), from(from), v(v), cost(cost){} bool operator < (
ALGORITHM NOTE カード
まず最初に、隣り合う２組の山を重ねるときの最小のコストを計算します（j = 1）。 i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。 つぎに、隣り合う３組の山を重ねるときの最小のコストを計算します(j = 2)。 i = 1, 2, 3 について計算します。 つぎに、隣り合う４組の山を重ねるときの最小のコストを計算します(j = 3)。 i = 1, 2 について計算します。 同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。 i = 1 について計算します。 各 j の値での最小コストの計算方法を考えます。 例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります： カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト ＋ それら２つの山を重ねるコスト (k = i
ALGORITHM NOTE 上司のおごり
典型的な動的計画法の問題です。 K[i] を i 番目の金額、 Ti[j] を i 番目までの金額を使って j を払えるかのフラグとする （1の場合に払えるものとする）と、 T0[j] を 0 で初期化し、 Ti[j] = Ti-1[j] | Ti-1[j - K[i]] となります。 あとは、i が素数で T[i] が 1 である i の最大値を求めます。 #include<iostream> using namespace std; #define KMAX 30 #define VMAX 1000000 int K[KMAX], T[VMAX+1]; void eratos ( int n, bool prime[]){ for ( int i = 0; i <= n; i++ ) prime[i] = false; for ( int i = 3; i <= n; i += 2 )
Nelder's Down-hill simplex method - 連続な多次元変数の最適化：滑降シンプレックス法
連続な多次元変数の最適化：滑降シンプレックス法 ここで説明するのはNelderらのDown-hill simplex methodです。 線形計画法の「シンプレックス法」ではありませんので念のため。 ポリトープ法（polytop method）とも呼ばれるらしいですが、よく分かりません。 遺伝的アルゴリズム（Genetic Algorithms: GA）は、その枠組みのシンプルさと 特に高次元の多次元変数を持つ最適化問題における探索性能の高さ、 多目的最適化問題への対応など、実問題の要求に答えることができる最適化手法として 広く認知されています。特に連続パラメータをビット列の遺伝子に直さずにそのまま用いる Real-coded GA (RGA) はかなり強力な手法として多くの実問題に用いられています。 小生は東工大制御工学科を92年に卒業し、卒論のテーマとして「ＧＡを用いた連続関数の最適化
手軽にTF/IDFを計算するモジュール - download_takeshi’s diary
情報検索の分野でよく使われるアルゴリズムで「TF/IDF」というものがあります。 ドキュメントの中から「特徴語」を抽出する、といったような用途でよく使われています。 TF/IDFアルゴリズムのくわしい解説はこことかここを見てください。 今回はこのTF/IDFの計算を「簡単」に実現するためのperlモジュールをCPANに上げましたので、ご紹介します。なまえはLingua::JA::TFIDFといいます。 Lingua::JA::TFIDF - TF/IDF calculator based on MeCab. http://search.cpan.org/~miki/Lingua-JA-TFIDF TF/IDF実装の困りどころ TF/IDFの実装を試みた方であればわかると思うのですが、実際にやろうとすると、TF（Term Frequency）の計算はなんら難しくありませんが、IDF（Inve
Simple-9について解説 - tsubosakaの日記
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,
転置インデックスの圧縮 - tsubosakaの日記
Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。 利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,603,176 ぐらいのサイズのデータです。 無圧縮の転置インデックスのフォーマットは 単語ID,文書数,文書1,....文書N, 単語ID,...で各項目4byteとなっており、1.5Gぐらいのサイズになっています。 これに対して各圧縮アルゴリズムを適用した結果は アルゴリズム 無圧縮 Variable Byte Code unary符号 γ符号 δ符号 Rice Coding pforDelta(仮) サイズ 1537MB 497MB 239475MB 474MB 407MB 367MB 455MB
RubyでAho Corasick - 森薫の日記
Ruby | 20:40 | Aho Corasick 法を読んで、そう言えばキーワードリンクに関していつか調べようと思っていたことを思い出しました。ライブラリのインストール今回はUbuntu 8.10にRubyからAho Corasickを利用するライブラリをインストールしました。 $ sudo gem install ruby-ahocorasick プログラムの実行以下のようなプログラムを作成して実行しました。ahocorasick-sample.rb require 'rubygems' require 'ahocorasick' keyword_tree= AhoCorasick::KeywordTree.new # ツリーを作成 keyword_tree.add_string("pen") # キーワードをツリーに追加 keyword_tree.add_string("This
オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？ 非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
Darts: Double ARray Trie System
Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています. ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことが
Post by @shyouhei
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
[O] 神嶌敏弘「推薦システムのアルゴリズム」
« 脳年齢テスト 整数の瞬間記憶 | トップページ 神嶌敏弘「推薦システムのアルゴリズム」 [日記] 神嶌敏弘さんの「推薦システムのアルゴリズム」を、人工知能学会誌を借りて通読しはじめたところです。 - 人工知能学会誌：目次 -- http://www.ai-gakkai.or.jp/jsai/journal/contents/ - Ｖｏｌ．２２ Ｎｏ．１（２００７年１月） - Ｖｏｌ．２３ Ｎｏ．１（２００８年１月） - Ｖｏｌ．２３ Ｎｏ．２（２００８年３月） に掲載されており、全部で40ページ以上。 なんで急に読み始めたのかというと、ある疑問が湧いたからです。 以下のようなコンテストが開催され、人工知能学会も協賛してるみたいなので、楽しいかもなと興味をもったのです。 - リコメンデーションコンテスト -- http://kgmod.jp/contest/ # 参
Slide 1
hillbig@is.s.u-tokyo.ac.jp 2005 12 z z / / z zSuffix Arrays, Burrows Wheeler Transform z zCompressed SA, FM-index z zWavelet Tree, XWT (Tree BWT) zSuccinct (bit array, tree) 1990 2000 2005 z z MEDLINE (1100 500GB) z Blog Watcher (1100 blog ) z TREC2004 Terabyte Track (2500 426GB) z Web Pages in Internet ( PB ) z Genome (> 800G in 2004) z We can obtain accurate information from very large inaccurat
Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://rgl.rubyforge.org/rgl/index.html
目 次 1. 準 備 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 1. 1 グラフ，ネットワーク · · · · · · · · · · · �