プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～
1. 2012/3/20 NTTデータ駒場研修所 (情報オリンピック春合宿) プログラミングコンテストでの データ構造２ ～平衡二分探索木編～ 東京大学情報理工学系研究科 秋葉 拓哉 1 2. 自己紹介 • 秋葉 拓哉 / @iwiwi • 東京大学 情報理工学系研究科 コンピュータ科学専攻 • プログラミングコンテスト好き • プログラミングコンテストチャレンジブック 2 3. データ構造たち (もちろん他にもありますが) • 二分ヒープ • 組み込み辞書 (std::map) • Union-Find 木 初級編 • Binary Indexed Tree コンテストでの データ構造１ • セグメント木 (2010 年) • バケット法 中級編 • 平衡二分探索木 • 動的木 本講義 • （永続データ構造） 3
指数時間アルゴリズムの最先端
Magnitude ~ extend the Euler Characteristics via Möbius Inversion ~Tatsuki SHIMIZU
指数時間アルゴリズム - てきとーな日記
指数時間アルゴリズムというのは，NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで，できるだけ指数の底の小さいアルゴリズムを開発することが目指されています． コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います． この分野は近年盛んに研究され始め，自分も大学でこの分野を中心に研究をしています． 今回，情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので，この分野の基礎的な手法から最先端の手法までをまとめてみました． 指数時間アルゴリズム入門@情報オリンピック春合宿講義 http://www.slideshare.net/wata_orz/ss-12131479 指数時間アルゴリズムの最先端(キャンセリング)@PFIセミナー http://www.slideshare.net/wata_orz/ss-12208032
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
スライド区間に対するクエリのまとめ
スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。まず、「スライド区間」の定義ですが、窓関数のようなものを想像してください。例えば、[2,5,10,-1,0,4,...]というデータに対してサイズ3の窓関数をスライドさせると、[2,5,10], [5,10,-1],[10,-1,0],.....と複数の連続する区間ができます。これらの区間に対して以下のようなクエリを考えます。 データサイズが小さい場合は愚直な方法で計算しても問題ありませんが、データサイズが大きい場合やオンライン処理で次々にデータが来る場合は高速な処理が求められます。天気予報システムや金融システムなどではこのような需要があると思います。例えば、ある時間幅内での最高気温・最低気温・平均気温を計算したり、リアルタイムに株価の高値・低値を計算するなどです。
麻雀ゲームが弱い理由（と羽生２冠が強い理由）～読みと見切り編～ - マッタリプログラミング日誌
先日の記事が割と評判が良かったようなので、続きを書いてみたいと思います。 前回は、局面の数に着目して麻雀の難しさについて書きましたが、今回は読みと見切り（探索と枝刈り）について紹介したいと思います。 将棋の場合：MIN-MAX法 将棋やオセロのようなゲームは、情報科学的には２人零和完全情報確定交互ゲームに分類されますが、このタイプのゲームではmin-max探索という先読みとαβ法という見切り（枝刈り）が有効であることが分かっています。 次の図のような感じです。 今、Ａという局面で先手の順番です。このとき先手にはＢ，Ｃという２つの手が考えられます。 先手がＢを指すと後手はＤとＥの２つの手が考えられ、先手がＣを指すと後手にはＦとＧという手が考えられます。 Ｄ～Ｇに書いてある数字はその局面で先手番からみた局面の有利さ（形勢判断）を数字化したものです。先手は出来るだけ数字が大きい局面に誘導したいで
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
大規模グラフアルゴリズムの最先端
2. 挨拶 • 自己紹介 – 秋葉拓哉 / @iwiwi – 東京大学 コンピュータ科学専攻 M1 – アルゴリズム系の研究室 – プログラミングコンテストが好き – 2009 年にインターンさせてもらって以来アルバイト アリ本 （グラフの話もあるよ） 1 3. いろんなグラフ 道路・交通ネットワーク • 頂点：交差点，駅など • 辺：道，路線など やりたいことの例 • 案内，交通管制 • 輸送や災害のための解析 • 地理情報と絡めたサービス • … 2 4. いろんなグラフ ソーシャルネットワーク • 頂点：人 • 辺：人間関係 やりたいことの例 • 「知り合いかも？」とか • 重要度・影響度の解析 • コミュニティ解析 • 情報の伝播力の解析 • … (MentionMap で作成) 映画 3
Story of Your Life » Blog Archive » 兎と亀のアルゴリズムをふと考えてみた
リストの循環チェックアルゴリズムといえば、兎と亀のアルゴリズムが有名だけど、ふと疑問がわいたのでさらっと検証してみた話。 時間も労力もかけたエントリではないけど、まぁいいかと。 兎と亀のアルゴリズムというのは、リスト構造を２つづつ辿るポインタ(兎)と、１つづつ辿るポインタ(亀)を用意して、兎が亀に追いつけば、そのリストは循環していると判断できるというアルゴリズム。 その話から最初に考えた擬似コードが下。兎が２つ進む間にちゃんと亀に追いついてるかどうかをチェックしている。 bool check(List *listp){ List *turtlep = listp; List *rabitp = listp; while(1){ turtlep = listp->next(); rabitp = listp->next(); if(rabitp == turtlep) return tru
pybrainでニューラルネットワーク入門 - mizchi log
勉強しつつ書いてみる。微妙な知識で書いてるので、おそらく間違ったことをたくさん書いてる。 まあせめて初学者らしく、初学者に通じるように平易な言葉で！ やりたいこと 関数(モデル)に乱数を与えて生成した訓練データから、元の関数の振る舞いを模倣(近似)できるようにする。 pybrain Pythonで扱えるニューラルネットワークのライブラリ、だそうで。 ギッハブからインスコ $ git clone git://github.com/pybrain/pybrain.git $ cd pybrain $(sudo) python setup.py install参考: 映像奮闘記: PyBrain - a modular Machine Learning Library for Python 概要 バックプロパゲーション(誤差伝搬法) 入力層 - 隠れ層 - 出力層の三層からなり、入力層のノードは
最長共通部分列(LCS) - 似非学問的な手記
最近更新が滞っている…… なんとかせねば（；ﾟωﾟ） なので少し細かな話題をば。 最長共通部分列問題（LCS）というものは、まあ動的計画法(DP)を学ぶとしたらまず確実に練習問題で出される問題で、「二つの文字列の共通部分列のうち最長のものの長さを求めよ」という内容です。 「部分列」なので、文字の取り方は文字列からとびとびになってもかまいません。 "abfhfr"の部分列として"aff"とかもアリです。 ただし、順番を変えてはダメ。 この問題を解くには、あまりにも有名な次のアルゴリズムがあります。 文字列str1(長さn)とstr2(長さm)に対し、 (1)二次元配列DPを用意する。 (2)DP[0][0〜m]とDP[0〜n][0]を0で初期化。 (3)二重ループでi,jを動かして、各DP[i][j]を DP[i][j]= max{ DP[i-1][j], DP[i][j-1], (str1
2つの期間が重なり合うかどうかを判定する。 - こせきの技術日記
2つの期間 A〜B と X〜Y が重なっているかどうかを判定したい場合。 のように4つのパターンがある。これを単純に、 A <= X && Y <= B || X <= A && Y <= B || A <= X && B <= Y || X <= A && B <= Yのように判定してはいけない。 Xは青い線の上を、Yは赤い線の上を動くとき、A〜B と X〜Y は重なり合う。この条件は、 X <= B && A <= Yこれで4つのパターンをカバーできる。ORは不要。始点と終点をわかりやすく書くと以下になる。 始点2 <= 終点1 && 始点1 <= 終点2アルゴリズムに名前がありそうな気がするけど、見つけられなかった。 (追記) 矩形の重なり判定の方が情報が見つかった。 * Life is beautiful: ビル・ゲイツの面接試験－私の場合 * 長方形の重なりを判定する問題 - ザ
GPU とグラフアルゴリズム その２ - 最適化問題に対する超高速＆安定計算
全対全最短路問題には Warshall-Floyd 法という有名な方法があるのだが、Dijkstra(ダイクストラ)法(１対全最短路問題）を点数の数と同じだけ繰り返して全対全最短路問題を解くこともできる。ところが、Warshall-Floyd 法は以下のようにメモリ要求量が厳しいので、グラフとしては小さい規模に属する DIMACS New York(NY) データ(264,346 点, 733,846 枝)を用いて解く場合でも、教科書通りにプログラムを作成すると 260GB ものメモリが必要になる。 最近では Warshall-Floyd 法を GPU 上に実装して全対全最短路問題を高速に解くという研究を見かけるようになった。上記の理由と現状の GPU のメモリ量を考慮すると中規模のグラフに対する Warshall-Floyd 法を GPU 上で実行するのは難しいので、小規模な問題で比較し
GPU とグラフアルゴリズム その１ - 最適化問題に対する超高速＆安定計算
アルゴリズムやデータ構造の性質から、グラフアルゴリズムは GPU との相性は良くない。しかし、以下の論文では苦手のグラフアルゴリズムを GPU でどれだけ高速化できるかということについて挑戦を行っている。多くの GPU の研究(特に国内)は明らかに GPU で性能が出しやすい題材しか扱っていないので、以下の論文のチャレンジ精神は賞賛に値する。 Large Graph Algorithms for Massively Multithreaded Architectures 以下は CPU 上でのダイクストラ法（最短路問題）の実験結果になるが、これと比較すると例えば全米データで１対全の最短路問題を解いたときに CPU では 5 秒程度で終了するが、GPU(Tesla) 上では 672秒かかっている（上記の論文の２３ページ）。ただし、５秒というのはかなり手間隙かけてプログラムを作成した場合の結果
最短路問題でよく見かける話題 - 最適化問題に対する超高速＆安定計算
最短路問題に関してアルゴリズムの教科書や授業や講演等で使用されている資料に以下のように書いてあるのを見かけることが多い。 １：ダイクストラ法においてはポテンシャル最小の点を見つける際に優先キュー（ヒープ、特に2-ヒープ)などを使用すると実行時間が速くなるが、フィボナッチヒープを使うとさらに速くなる。 ○点数を n, 枝数を m とする。2-ヒープでは計算量が O(m log n)、 フィボナッチヒープを使うと O(m + n log n) になるのだが、実際にはフィボナッチヒープを使うと実行があまり速くならない（むしろ遅い）。実用的に高速なのは ヒープ(heap)、バケット(bucket)、マルチレベルバケット(MLB)あたりのデータ構造である。 ２：全対全最短路問題に対しては、１対全最短路問題に対するダイクストラ法を点の数だけ繰り返すよりもワーシャル・フロイド法(Warshall-Flo
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
Bal4u : C/UVa - LIS/LDSの計算
ESMAJ