各種 DP を愚直な形で考えてみる - えびちゃんの日記
先日、下記の記事でナップサック問題の DP を愚直に眺めました。 rsk0315.hatenablog.com 今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○（何らかの集合）の最大値」のように計算せず、○○の部分について考えていきます。 もちろん DP をする際に○○をそのまま持つと空間計算量がめちゃくちゃになる（ことに伴って時間計算量もめちゃくちゃになる）のですが、典型 DP で暗に構築されている集合を考えておくことで、そうした構造を持つ DP を考える際に理解がスムーズになる気がします。 「何々を全パターン考慮したい」となったときに「こういう漸化式を考えればよいはず」とできるレパートリーが増えそうです。 想定読者は競プロをしていて DP を学び中・苦戦中〜ある程度知っている人で、ある程度数式を読める人です。数式が苦手な人は、数式が得意な人に助けてもらうなど
興味深いデータ構造：BK木 | POSTD
BK木とは、 距離空間 内のデータをインデックス化する目的に特化した、木構造を指します。距離空間は基本的に、要素の組 $ (a,b) $ 全てについて距離関数 $ d(a,b) $ を持つオブジェクトの集合です。この距離関数は正しく動作することを保証するために、一連の公理を満たしていなければなりません。これが必要になる理由は、後述の「検索」のセクションできちんと説明します。 BK木のデータ構造は、一連のキーを検索し、与えられた検索キーの値に最も近いキーを見つける問題の解決策として、 1973年にBurkhardとKellerが提案したもの です。この問題を解決する素朴な方法は、要素の組に含まれる各要素と検索キーの値を単純に比較することです。一定の時間内に比較が完了した場合、この検索の解は $ O(n) $ となります。一方、BK木を採用すると、この時実行する比較の回数を減らせる可能性が高く
Common Subsequence 解説
問題名：Common Subsequence (PKU) 出典：Southeastern Europe 2003 難易度：☆☆☆ 問題の種類：DP 解法：LCS (Longest Common Subsequence) 解答ソースコード： 1458-deq.cpp アルゴリズムの概略 DPの四天王（？），LCS (Longest Common Subsequence) そのままの問題です。 アジア地区予選など，通常はこれをひねった問題が出てきます。 LCSとは，二つの値の列（この問題では文字列）が与えられて，最長の共通部分列を見つける問題です。 部分列は連続している必要はありませんが，順序は変更してはいけません。 例えば X = "abcfbc", Y = "abfcab" であればLCSは "abfc" や "abcb" になります。 LCSは一般的に複数ありえますが，この問題ではその長
初級グラフアルゴリズムをまとめてみる - テストステ論
一週間前から集中的にプロコン勉強をしている. まるで受験生だ. 楽しい. とりあえず, 以下の3冊の本をざっくり見ると, カバーする範囲において, 蟻本(<=初級) =~ ALDS(全部) =~ 最強最速(全部)というのが大体成り立つと分析した. すなわち, この範囲が極めて大切だということだと解釈した. プログラミングコンテストチャレンジブック(蟻本) プログラミングコンテスト攻略のためのアルゴリズムとデータ構造(ALDS) 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド(最強最速) 時間的に, 蟻本の中級以上の範囲を学ぶことは不可能だし, どうも体系立ってない領域に思えたので, 学習方針としては, 初級範囲をきっちり学んで, それで落ちたら諦めるということにした. さて, 初級において特に重要なことは, 動的計画法(DP) グラフアルゴリズム である
第5章 パーサコンビネータ―小さなパーサを組み合わせて大きなパーサを作る | gihyo.jp
この章では、関数型の至宝であるコンビネータライブラリについて説明します。 コンビネータとは何か？ この章でいうコンビネータとは、ある型の部品と部品を組み合わせて、同じ型のより大きな部品を作るための関数のことです。たとえば、パーサのコンビネータライブラリは、パーサを組み合わせるための各種コンビネータを提供しており、簡単にパーサを作成できます。コンビネータライブラリは、言語内DSL（Domain Specific Language）と表現してもよいでしょう。 関数型では、パーサに加えて、データを文字列でわかりやすく表示するプリティプリンタ、SQL、XML、ハードウェア記述、そしてデリバティブ（金融商品）記述、楽譜記述など多様なコンビネータライブラリが作られ、実際に使われています。この章では、パーサのコンビネータライブラリを取り上げます。 CSVのパーサ たとえ簡潔でも、実用的でないパーサの例だ
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
充足可能性問題のアルゴリズム
充足可能性問題（satisfiability problem）とは？ 充足可能性問題（以下，ＳＡＴ問題と略す）とは， 理論計算機科学で最も基本的で 重要な ＮＰ完全問題 の一つである． グラフ理論における 巡回セールスマン問題，頂点彩色問題，独立頂点集合問題， オペレーションズ・リサーチにおける整数計画問題， ゲーム・パズルにおける数独，テトリスなど， 実社会で遭遇する多くの（決定）問題がＮＰ完全問題である． その中でも， ＳＡＴ問題は，そのＮＰ完全性が示された最初の問題である． 以下の意味で， ＳＡＴ問題は，ＮＰ完全問題の根本である： すべてのＮＰ完全問題のＮＰ完全性は， （いくつかの例外を除いて） ＳＡＴ問題からの有限回の多項式時間還元を経て示された． 例えば， 教科書 [1] では， ハミルトン閉路問題は， 頂点被覆問題からの多項式時間還元により， 更に， 頂点被覆問題はＳＡＴ問題か
Trie が提供すべき操作について検討してみる
nokuno さんの記事「オープンソースのTrieライブラリまとめ」あたりを参考に、まず既存の Trie ライブラリ群がどのような API を提供しているのかを調査し、その上でこれから Trie を実装する場合に、どのような操作・API を提供すべきかを検討した結果のメモです。 記事にあるすべての Trie 実装を確認するのはしんどいので、代表的な感じのものを適当にピックアップしてみました。 Tx ... 岡野原さんによる簡潔データ構造を利用した Trie の実装。 prefixSearch() ... prefix search。Trie に格納されている文字列の中で、対象文字列の接頭辞としてもっとも長く一致する文字列を探し出す。common prefix search で列挙される文字列のうち、長さが最長のものと同じ。 commonPrefixSearch() ... common p
原理的な決定不可能性とはどういうものか - 数学屋のメガネ
決定不可能性というのは、ある判断が確定しないということを意味する。世界のあり方として、いくつかの選択肢が考えられるとき、その選択肢のどれが実現しているかということが確定しないとき、現在の状態は決定できないと考えられるだろう。この決定できない・確定していないという状況は、現実を対象にしてそれを認識しようとすればいつでも遭遇するようなもののように感じる。 「一寸先は闇」ということわざがあるように、未来については決定していない・確定していないと普通は考える。だが、ある種の未来に関しては、現在の状況のいくつかの側面を把握することによって、未来がどのような状況になるかが決定的・確定的に語れることがある。自然科学による予測は、誤差を捨象する限りで１００％確実な予想を与える。決定可能な対象が存在するということは、決定不可能性の中に、原理的な不可能性と現象的な不可能性があるということを考えさせる。 現象的
Sorting Algorithms Animations
KEY Black values are sorted. Gray values are unsorted. A red triangle marks the algorithm position. Dark gray values denote the current interval (shell, merge, quick). A pair of red triangles marks the left and right pointers (quick). DISCUSSIONThese pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates.
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
共通部分文字列をカウント | アルゴリズム [AOJ 528][Ruby/Python][文字列操作]
引き続きプログラミングの基礎体力づくりと、Pythonの勉強を兼ねてアルゴリズムを勉強中です。今回は『共通部分文字列をカウントする方法』について勉強しました。AIZU Online Judgeで対応している問題は、『Common Sub-String』です。アルゴリズムというよりは頭の体操的なパズル問題ですが、ある程度速度の早いプログラムを書くのには工夫が必要だなと痛感しています。 🏈 AOJ問題Common Sub-String Aizu Online Judge。2個の文字列が与えられたとき、 両方の文字列に含まれる文字列のうちもっとも長いものを探し、 その長さを答えるプログラム。 🍄 Rubyコードloop do s, t = gets.chomp, gets.chomp rescue break s, t = t, s if s.length > t.length max_l
![共通部分文字列をカウント | アルゴリズム [AOJ 528][Ruby/Python][文字列操作]](https://cdn-ak-scissors.b.st-hatena.com/image/square/c2ea7e72d0d7f3ba6c237909f321e67ffbdaa24e/height=288;version=1;width=512/https%3A%2F%2Fmorizyun.github.io%2Fimg%2Fog_image.png)
通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 - あのねノート。
2014-01-31 通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 まとめ やり方 まえおき まえおき は みつかりませんでした。 深さ優先探索の例 例から入る 0という名前の点から探索を始める 0につながってるのは1か2か3だけど、テキトーに3を選ぶ 3につながってるのは0か4か5だけど、0は訪問済みなので選択肢は4か5 テキトーに4を選ぶ 4につながってるのはは2か6だけど(3は訪問済み)、テキトーに2を選ぶ 2につながってるのは0と4だけど、どっちも訪問済み 直前に来た4に戻って行けるとこを探す 4につながってるのは2と3と6だけどまだ行ってない6を選ぶ 6から行けるとこはどこもない(4は訪問済み) 戻って4から行けるところを探すけどどこも訪問済み 更に戻って3から行けるところを探す 5を選ぶ(0と4は訪問済み) 5から行けるとこはどこもない(3は訪問済み) 戻って
アルゴリズム入門以前 - 武蔵野日記
朝から雨で娘の機嫌が悪い。昨日病院ではずっとおとなしかったのだが、その反動だろうか？ 先週末にエアコンの調子が悪かったのは無事修理できたのだが、また寒い日に戻ったようで（梅雨入りしたらしい）、エアコンフリーの生活。これくらいの気温が続いてくれればいいんだけどな〜 松本研の年報の巻頭言が更新されたようである。松本研が博士前期課程の学生を受け入れ始めてから去年で20年（残り7年）ということで、自分も今年に初めて博士前期課程の学生の入学・進学があり、残り29年。松本研はスタッフも含めた OB/OG が200人以上いるそうだが、自分が博士後期課程に進学してからは毎年10人以上博士前期課程の学生が入学してくるので、定年までに300人に到達しそうである。うちは毎年4〜8人くらい（平均的には6人くらい？）だと思うので、定年までいても200人にはならないだろうな〜。 そういえば、先日「世界でもっとも強力な
ゼロから始めるDeepLearning_その1_ニューラルネットとは - 分からんこと多すぎ
対象とする人 ディープラーニングすごい！ ←聞き飽きた チュートリアルあるよ！ ←ふわっとしすぎて具体的なところが分からん こういう論文あるよ！ ←読めるわけないだろ そういう人向け。（たぶん学部四年程度向け） ニューラルネット初学者が、書ききるまで怪しいところ満載でも突っ走ります。 ニューラルネット（この記事） →（AutoEncoder） →（DenoisingAutoEncoder） →ホップフィールドネットワーク →ボルツマンマシン →Restrictedボルツマンマシン →（Gaussian Binary - Restricted Boltzmann Machines） →（DeepBeliefNetwork） →（DeepNeuralNetworks） →畳み込みニューラルネット（後日） までやる。 太線以外は読み飛ばしてOK 本文中では怖い式は使わない。（Appendixに書
数あるソートアルゴリズムをビジュアル化し堪能できるサービス「SORTING」
大小の関係が決められたデータを小さい順や大きい順に並び替える作業はソートと呼ばれ、コンピュータには欠かせないプログラムです。そのため、ソートをより早く・確実に・効率良く実行できるように、さまざまなアルゴリズムが考案されてきました。そんなコンピュータの発展にかかせない役割を果たしてきたソートアルゴリズムをビジュアル化することで直感的に理解できるのが「SORTING」です。 SORTING http://sorting.at/ これがSORTINGのサイトページです。ソートアルゴリズムを選択してページ下の「PLAY」ボタンをクリックすると、そのソートアルゴリズムを使ってボールが並び替えられます。 たとえばアルゴリズム「クイックソート」でランダムに並んだ状態の大きさの異なるボールを左から小さいもの順に並び替えるとこんな感じです。 選べるソートアルゴリズムは、クイックソート・ヒープソート・スムース
PythonでBag of WordsとSVMを使ったタイトルのカテゴリ分類 - stMind
cc licensed ( BY ) flickr photo shared by Loco Steve 週末に試そうのコーナー。 ちょうど良いチュートリアルがあったので、データセットを用意してやってみました。 問題 How can I get a computer to tell me what an article is about (provided methods such as bribery and asking politely do not work)? ある記事が何について書かれているのか、コンピュータに理解させるにはどうすれば良いか? チュートリアルでは手動で作ったデータを使って犬もしくはサンドイッチの2クラス分類をしています。 ここでは、Google NewsでiPadのニュース、ソチ五輪のニュースとカテゴリ分けされている記事のタイトルを使って、 あるタイトルがiPa
言語処理学会年次大会で文法圧縮チュートリアル講義をしてきました - Preferred Networks Research & Development
まるまるです。春がきてますね。東京はだいぶ暖かくなってきました。 先週（3/17〜3/20）行われた言語処理学会第２０回年次大会（NLP2014）において「文法圧縮入門：超高速テキスト処理のためのデータ圧縮」というタイトルでチュートリアル講義をさせて頂きました。 講義資料はSlideShareで公開しています。 文法圧縮とは、文字列を木構造に変換し、その木構造に含まれる冗長部分を文脈自由文法の生成規則として集約させて表現する圧縮法です。この圧縮法は近年の文字列アルゴリズム業界で注目を集めており、主に以下の様な特徴があります。 冗長度の高いデータ（例えばゲノム集合、バージョン管理文書、ウェブアーカイブなど）を効果的に圧縮できる。 圧縮したまま高速に検索処理などを行える（圧縮文字列処理）。 木構造などのデータ構造の圧縮にも使われる（圧縮データ構造）。 NLPとは直接結びつかない内容ですが、文字
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
文字列探索アルゴリズム談義
