テキトーなメモ帳

テキトーなメモ帳

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>…