テキトーなメモ帳

テキトーなメモ帳

LOUDS-trieを実装してみた

何年前のネタだよって感じですが、『日本語入力を支える技術』のサンプルコードを参考にとても原始的なLOUDS-trieをC++で実装してみました。 原始的なというのは、select,rankが定数時間でできなかったり、日本語入力に対応してなかったりするというあたりで…

BFGSを実装してみた

BFGSを実装してみました。 BFGSとは準ニュートン法におけるHesse行列の逆行列の近似手法の一つです。 って言われてもよくわからないかもしれません。 機械学習のほとんど(CRF,MaximumEntropyなど)で行われているのは目的関数の最適化なのですが、その際の偏…

YAPC::Asia 2015 に行ってきた

Larry Wallのサイン欲しさにYAPC::Asia 2015に行ってきました。 2日目だけ参加しました。 以下、聴いたスピーチと感想です。 Perl 5.22 and You 普段わりとPerl使ってるのに、5.20以降サブルーチンの書き方がちょっと現代的になった(my ($foo,$bar) = @_;な…

高村本の条件付確率場(CRF)と最大エントロピー法を実装してみた

やっぱり読んでるだけではだめだよね?ということで、かれこれ3か月ぐらい前に高村本(言語処理のための機械学習入門)の章末問題を全部やりきりました。 というわけで、今度は実際に実装するときだろうと考えました。 最大エントロピー法については重みベ…

AOJ:0211 Jogging

全員の一周分の距離を統一します。 そして、各生徒の速度に「統一後の距離 / 元の距離」をかけてあげて、距離が増えた分速度を増加させます。 そうすると各生徒の速度の比が、そのまま出力するべき各生徒の周回数になります。 では、どうしてそうなるのかを…

AOJ:1519 Room of Time and Spirit

Union-Find木を使って精神と時の部屋に入る前の戦士の初期値の相対関係を管理するのがポイントです。 どうやって戦闘力の初期値の相対関係を算出するかというと、 INコマンドが実行されるたびに、Ao:精神と時の部屋の発生以前に、戦士Aが持っていた戦闘力(つ…

AOJ:2312 Magical Girl Sayaka-chan

動的計画法です。 まず音符を音楽的美しさ順でソートします(昇順でも降順でもどっちでもいい、ソースコードだと降順なのでこっちで説明していく。) 以下ソート後の各音符の順番のことをindexとします。 つぎに、index::=0の音符を始点とし、音楽的美しさ順…

AOJ:2292 Common Palindromes

SuffixArrayによる最長回文の検知+SegmentTreeによるLCPの保存・算出+UnionFindTreeを利用したS・T両方の文に出現する回文の数の計算 の豪華三本立て SuffixArrayによる最長回文の検知については下記のページ(なにかの雑誌の記事?というかなんだかアクセ…

AOJ:0271 Izua Dictionary

わけがわからなかったので、いろんな方のコードを読んで研究(?)した結果、 辞書順での位置を探したい単語の文字を最右端から左へむかって走査していって、 [現在走査している位置よりも右側にあり、かつ数字が小さいものの個数] * [現在走査している位置…

AOJ:0233 Book Arrangement

例えば-1944の1の位の数を-10進数変換したいとき 単純に余りを求めようとすると、 -1944 / 10 = -194...-4 となってしまうので上記の演算結果の余りに対して10を足して -1944 / 10 = -195...+6 となるようにするのがポイント #define _USE_MATH_DEFINES #de…

AOJ:1227 77377

コスト最小法(形態素解析で使われているアルゴリズム)(参考:Viterbi-Algorithm:http://en.wikipedia.org/wiki/Viterbi_algorithm) からスコアの計算とTrieによる照合とA-starによるバックトラックをやる部分を無くした感じで解きます。(つまりラティス…

AOJ:2444 Substring

ローリングハッシュ(http://en.wikipedia.org/wiki/Rolling_hash)という関数を用います。 Hをハッシュ関数、S(x)を入力文字列におけるx番目(1-based)の文字を返す関数、 S(l,r)を入力文字列におけるl〜r(1 そうすると、ハッシュ関数Hが任意の部分文字列S(l…

AOJ:1318 Long Distance Taxi

ダイクストラ法で解きます。 ステージの探索において dp[現在訪れている都市のID][現在の残りの燃料]:=すでに訪れたか否か をメモしていけば大丈夫です。 ・・・が、このメモをダイクストラ法における、次の遷移先のノードへ分岐していく箇所、 つまり for(i…

AOJ:2212 Stolen Jewel

Aho-Corasick法による文字列の照合とBFSで解きます。 はじめは、禁止パターンとの照合なんてTrieを使えば十分なのになんで皆さんAho-Corasick法(Trieを拡張したデータ構造を利用する方法)なんて実装してるんだろうか?と思いました。 でも、Trie(DoubleArray…

AOJ:0590 Available Areas

まず、与式を式変形して、xの式とyの式を出すと(Aは面積)、 2*x*y+x+y=Aよりxの式は x*(2*y+1)+y=A x=(A-y)/(2*y+1) yの式は y*(2*x+1)+x=A y=(A-x)/(2*x+1) よって、部屋の面積が正しいかどうか見るためには yの式を使って(A-x)%(2*x+1)==0(もしくはxの式…

AOJ:2525 Change

手元に残る日本円を最大化するための手段として考えられるのは次の2つ 各国に対して余分に投資して、為替差益で儲ける 各国に対して必要経費分のみ払う。 で、為替差益で儲けることはできるのか?というと 投資先の国をC国、余分に投資した金額をx円、為替…

AOJ:2401 Equation

構文解析+変数のTrue/Falseのパターンを全探索です。 ~演算子と!演算子の使い方を間違えてWAを連発したおかげで bool変数のサイズは1バイト(自分の環境(g++ 4.7.2)では)ということを今更知りました(1ビットだと思ってた)・・・ ということは、 bool val1…

AOJ:2504 Statement Coverage

構文解析+2-SATを強連結成分分解で解きます。はじめ、乱択アルゴリズムを使ってなぜかTLEしないで解けてしまいました。 (ちゃんと2-CNFに変換しないでやったので、なんちゃって乱択アルゴリズムというべきか・・・) 構文解析はそれほど面倒ではありません…

AOJ:2197 Sum of Consecutive Integers

1から始まる並びを足してnになれるか、2から始まる並びを足してnになれるか、3から始ま(ry を順々に見ていけば大丈夫です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #inc</queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:2185 Petting Cats

衝突判定に近いです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #includ…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:2186 Heian-Kyo Walking

典型的な動的計画法です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #incl…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:2104 Country Road

初め全家庭につながっていた電線を、発電所を追加していくことによってどんどん削除していくイメージです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:2103 Battle Town

問題文通りに実装するだけです。 switch文使わないほうが良かったですね・・・ #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #inclu</string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:2102 Rummy

まるで麻雀。色でソート→数字で昇順にソート。 数字の並びのパターンは全部で4つ ①122223333のような4連続で同じ数字が揃っているカードを含む並び(4:1:4なども当然ある) ②333のような3連続で同じ数字が揃っているカードを含む並び ③123のような3連続で数字…

AOJ:2101 Perfect Number

試行除算による素数の求め方にかなり近い感じがします。 数字iがnの約数(つまりn%i==0)であればn/iもnの約数という性質を利用すれば、計算量が減らせます。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #inc</cmath></sstream></iostream></cstdio>…

AOJ:1092 Make KND So Fat

動的計画法です。cost[x] : その日に、x円で達成出来る最大の重さ dp[i+1][j] : i日目までで、j円使った時の最大の重さ #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:1091 KND is So Sexy

ADC及びBECの各辺の長さを誤差が大きくならない程度に全探索。 →各辺の長さを使ってヘロンの公式で面積を出す。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #incl</stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:1063 Watchin' TVA

日をキーにして見るべきアニメをmapに入れるまず、みなければならないアニメをちゃんと見ることが出来るか走査。 これは全探索でok。また、このとき、このアニメが占有している時間に印を付けておく。次に、そうでもないアニメがどれだけ見れるか走査。 #def…

AOJ:1017 Riffle Shuffle

問題文通りに実装するだけ。 dequeを使うと楽です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #incl…</cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0518 The Oldest Site

正方形の候補になりうる二点を全探索 →実際にちゃんともう二点あるかチェック(4点ないと正方形が作れないから) →最大面積を求める #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #incl</algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:0527 Setting Go Stones

問題文通りに実装するだけです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #i…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0571 JJOOII

Jが来た→以前の文字がJ以外なら全ての履歴をリセット Oが来た→以前の文字がIなら全ての履歴をリセット Iが来た→とにかくプッシュで、一文字読み込むごとに常にレベルNの部分文字列がちゃんとできてるか判定を行う #define _USE_MATH_DEFINES #define INF 0x3…

AOJ:1074 Popularity Estimation

問題文通りに実装するだけです。 #include <string> #include <iostream> #include <sstream> #include <map> #include <cmath> #include <string> #include <vector> #include <limits> #include <algorithm> using namespace std; int main() { vector<pair<int,string> > res; while(1){ int n; map<int,int> time; map</int,int></pair<int,string></algorithm></limits></vector></string></cmath></map></sstream></iostream></string>

AOJ:1056 Ben Toh

動的計画法です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include …</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1078 SAT-EN-3

充足可能性問題?これは、乱択アルゴリズムの出番なんじゃないか?と思って解き始めましたが この問題は入力をパイプでsplitした後、再帰下降構文解析するだけです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #incl</sstream></iostream></cstdio>…

AOJ:2400 You Are the Judge

問題文通りに実装するだけです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #i…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1085 Spellcasters

魔力で魔法使いをソートして 魔力iより大きい魔力を持つ魔法使いの位置-魔力i以上の魔力を持つ魔法使いの位置 を求めていくと魔力iを持つ魔法使いの数を割り出すことが出来るようになります。あとは、これを利用して、魔力の合計が目標値になるような組み合…

AOJ:1266 How I Wonder What You Are!

正直、問題文中の Let us defie that θi,j is the angle between the direction of the i-th star and the center direction of the j-th telescope and φjis the angular radius of the sight field of the j-th telescope. という一文が全く理解できません…

AOJ:0517 Longest Steps

白紙が含まれないときは、しゃくとり法。 それ以外は、計算量が10000*(1+10000)/2≒5*10^7の全探索 という変なアルゴリズムですが通りました。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #includ</cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:0054 Sum of Nth decimal places

入力された数を10倍 整数化 10で割ったあまりをとる を繰り返します。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include </string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0069 Drawing Lots II

全探索です。 横棒を一つ追加したパターンを全通り試します。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #in…</cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:0012 A Point in a Triangle

面積を利用して(xp,yp)が三角形の内部にあるか判定します。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #…</cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1214 Walking Ant

ダイクストラ法です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #includ…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1120 Pile Up!

大分面倒ですが、問題文通りにシミュレーションです。 dequeの配列を使いました。 キューブごとに床を持っているとします。 配列の位置iは、i番目のキューブがはじめに置かれていた床の番号と一致しています。 また、配列の位置iにi番目のキューブが一つだけ…

AOJ:1217 Family Tree

各ノードの親のノードを記録した木構造を作っていきます。 一番注意するべき点は各入力文の末尾のピリオドです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #inc</stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:1216 Lost in Space

全探索です。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include </set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1218 Push!!

ダイクストラ法です。 コスト、the cargoの位置、the warehousemanの位置をキューに入れて回していきます。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>…

AOJ:1275 And Then There Was One

シミュレーションです。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #inclu…</set></cstring></string></map></limits></stack></queue></algorithm></cstdlib></cmath></sstream></iostream></cstdio>

AOJ:1276 Prime Gap

与えられたある整数が素数→0を返す それ以外→lower_boundで、与えられたある整数以上の最初の素数の位置を探す(と同時に一つ前の位置も分かる)。→ギャップを返す #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #include <iostream> #include <sstream> #includ</sstream></iostream></cstdio>…

AOJ:1285 Grey Area

該当バーのインク使用量=該当バーの暗さの階調*(その該当バーの範囲の値の出現頻度)/(高さ最大のバーのその範囲の値の出現頻度) という式を解いていきます。 最後に0.01を足すのを忘れずに。 #define _USE_MATH_DEFINES #define INF 0x3f3f3f3f #include <cstdio> #</cstdio>…