近況
お久しぶりです．
最近いろんなことが怒涛の勢いで押し寄せてきて全く更新ができていませんでしたが，少し落ち着いたので，軽くまとめておきたいと思います．
3月
卒業が確定したようなので，月初めに1週間ほど卒業旅行に行きました．
行き先はイタリアでした．
これに関しては，ヒマさえあればまとめたいような気もしています．
帰ってきた後は，学会発表しながら論文提出してました．
論文のターゲットは日本の学会のはずなのに，なぜか英語で執筆しました．
通ってるといいな……
大学院を卒業しました．
授業，就活，研究であっという間でしたが，充実した2年間でした．
引っ越しました．
東京住まいです．
駅近ですが家賃高いです．
4月
就職しました．
一応「大手」と言っていい感じのIT企業です．
現在研修中です．
アニメ見るヒマがなくてつらい……
年度初めに立てた2週間おき更新ルールを最後の最後で守れなかったのですが，ネットが使えないのは仕方ないですよね（言い訳
今後は2週間おきだと辛いですが，何かあれば（不定期に）このブログを更新していきたいと思ってます．
よろしくお願いします！
アニメ・声優のデータベースをまとめたかった
この情報は2015年2月現在のものです．
この記事は必要に応じて加筆・修正される可能性があります．
また，Webスクレイピングに関しては，著作権法に抵触しない形で行われる必要があります．
修論の研究の合間にちょくちょく進めてたことを書いときます．
私自身，データを扱う研究室にはいるのですが，あまり大きなデータを扱うような処理を行ったことはなく，そういうことができる機会がないかなと思っていました．
どうせなら，自分が好きな分野で解析ができた方が楽しいだろなーということで，アニメやゲーム，声優あたりのデータ解析をしようと思いました．
その第一段階として，どのようなDBが存在するのかをまとめたので，晒しておこうと思います．
特に，プログラムからの2次利用がしやすいかという観点に着目しています．
網羅度は低いです．
アニメ・声優に関するデータベース
アニメ作品データベース
ざっと探してみたところ，すぐに2次利用できる形でのDBはないようです．
Wikipedia
Wikipediaが日本語化された頃から，アニメに関する記事は多かったような気がします．
基本情報に加え，あらすじや登場人物，放送情報など，多種多様な情報が掲載されています．
強力なDBであることは間違いないのですが，記事にIDなどが振られておらず，URLによるアクセスがしにくいことと，HTMLのエレメントにIDなどが付されていないため，スクレイピングが難しいことなど，2次利用という点ではなかなか使いづらいのではないかと思います．
また，記事による記述量のむらが大きいことも難点です．
.lain
声優と，その出演作品についてのデータベースです．
作品ごとにIDが振ってあり，URLによってアクセスできるなど，比較的2次利用のしやすい形でデータが保存されています．
アニメ作品に関して使えるデータとしては，スタッフとキャストなど，最低限のものに限られますが，網羅率が高く，現在も更新が続いているので，なかなかいい情報源なのではないかと思います．
作品データベース
こちらは，アニメだけでなく，ゲームやマンガ，映画など，様々な媒体のデータを保持しています．
こういう「何でもDB」にありがちな網羅率の低さもなく，制作会社の情報も確認できるみたいですが，URLによるアクセスがしにくいことと，フォーマットがまちまちのため，2次利用という点ではマイナスです．
アニメ放送情報データベース
アニメ番組表 API
各都道府県ごとに，アニメの放送時間，放送局などが閲覧できます．
このサービスの強い点は，なんと言っても，WebAPIによる外部からのアクセスが可能な点です．
XML，JSONといったおなじみのフォーマットで，放送情報を取得することができます．
速報性に乏しいという弱点があるようですが，十分に使えるサービスだと思います．
しょぼいカレンダー
タイムテーブルの形式で，アニメの放送情報を閲覧することができます．
情報が見やすい形に整えられていることと，放送時間変更などの情報も比較的早く反映されるため，私も普段のアニメ放送情報を調べるのに使っています．
また，再放送の情報や，一部のオタク向け番組の情報なんかも追われているようです．
2次利用という観点からだと，HTMLのエレメントにID等は振られているので，利用は可能ですが，そこまで適した形というわけでもないようです．
声優データベース
Wikipedia
声優に関しても，アニメとほぼ同様のことが言えます．
一応，アニメに比べると記載する内容がある程度限られるため，うまくCSSセレクタなどのルールを作成すれば，出演作品リストぐらいは機械的に取得可能かなと思います．
.lain
声優に関しても，.lainは強力なDBだと思います．
誕生日や年齢といった基本情報や，共演情報の検索なんかもできたりします．
シゲムラさん
声優のブログ，Twitterなどのアンテナを掲載しています．
速報性に関しては，こちらの方が上かもしれません．
まあ，少なくともTwitterに関しては自分でアカウントを作って直接フォローした方が早いという説もありますが…
まだまだサーベイが足りてないと思うので，何か知っているDBがあったら，コメント等で教えていただけると助かりますm(__)m
Microsoft Academic APIのRubyラッパを作成した
特に更新することもないので(またか)，以前に紹介した，Microsoft Academic APIのラッパを晒しておこうと思います．
以前の記事はこちら．
こちらがコード．
研究用プログラムはRuby on Rails上の実装なので，こちらもRubyでのコードとなっています．
実際には，キャッシュ用のコードをかませて，APIの呼び出し回数を減らすようにしています*1．
上のコードの例では，Haveliwalaの"Topic-sensitive PageRank (WWW '02)"について，タイトル，発行年，著者，URL，引用論文集合，被引用論文集合を表示するようにしています．
ここで言う，「論文ID」は，以前の記事で説明した，Microsoft Academic API上で一意に振られているIDとなります．
このAPIがpublicなものなのかはよくわかっていませんが，特に登録などをすることもなく使用することができるようです．
昨年のまとめと今年の抱負
あけましておめでとうございます．
こういう時でもないとできないので，去年の簡単なまとめと，今年の抱負を垂れ流していきたいと思います．
去年のまとめ
1月
年始早々から就職活動．
正月もSPIの勉強とかしてた気がする．
この頃から東京に行く回数が増えてやたら面倒だった．
2月
就活しながらインターンしながら修論中間発表に向けて研究してた．*1
世の中には自分と歳変わらないのにすごい人もいるもんだなと思った．
東京でのインターン終了後とんぼ返りからの翌日中間発表会の流れにはさすがに参った．
第一志望の企業の選考に落ちた．
この時期が体力的にも精神的にも最も病んでいた．
3月
学会発表で他大の知り合いに会った．
ちょっと慰めてもらった．
今の内定先の役員の方と(内定後に)お話させてもらう機会をいただいた．
自分を高く買ってくれていることを感じ，入社することに決めた．
4月
就活からの開放感の中だらだら．
この時期に結構技術書を読んだ．
友だちに誘われ，競技プログラミングを始めた．
内定先のイベントで，RubyのMatzさんと会ってお話した．
気さくな方で良かった．
はてなブログに引っ越し，2週間に1度の更新を目標に書き進めた．
5月
TOEICの勉強とか．
この時期は英語の勉強のモチベーションが高かった．
6月
マカオの国際学会に参加してきた．
海外は初めてだったので，知らないことも多かったが，いい経験になった．
お金と時間さえあれば，もっと海外行きたい．
7月
KUPCへ参加．
成績は散々だったが，ここらへんからプロコンへのモチベーションが上がってきた気がする．
8月
らぼの同期と九州旅行に行った．
今は噴火中で行けなくなってる阿蘇山火口を見た．
日本じゃないっぽかった．
あと，長浜の屋台のラーメンが美味かった．
学会論文を1本書いた．
実験の進捗が悪く，一時期は落とすのも覚悟したが，何とか間に合った．
9月
中間試問に向けて研究してた．
といっても，やりたいことは8月中に大体やってしまっていたので，9月に苦労することはあまりなかった．
ネットワークスペシャリスト試験の勉強を始める．
自分に知識がなくて結構厳しそうだった．
10月
内定式に参加した．
「ああ，とうとう僕も社畜になってしまうのか…」と感じた．
2次会がチャラくてついていけなかった．
東京から帰る前に友達とスカイツリーの中で飲んだビールが美味しかった．
ネットワークスペシャリスト試験を受けた．
情報セキュリティスペシャリスト試験に近い問題だったので，行けそうな気がしたが，結構な得点調整が入ったらしく，落ちてしまった．
11月
8月に書いた論文が採択されたので，東京の学会に参加してきた．
就活中にお会いした人も結構いて，挨拶してきた．
12月
CODE THANKS FESTIVALに参加してきた．
100人程度中，9位入賞だった．
「自分もプロコンやってていいんだ」と思った．
アニメ「SHIROBAKO」にドハマりしてBDを買った．
思えば，去年は，自分の中でも色々と価値観が揺れ動いた年でした．
就活に関しては，「これから何して生きていこう」ということを本気で考えるいい機会になったと思います．*2
就活の終了後は，比較的ヒマな時間が続き，人生のモラトリアム最後の期間を楽しめたのではないかと思います．
今年の抱負
今年の目標は，「時間を大事に使う」です．
6年間の学生生活で感じたこととして，「自分は〆切がないと動けない」ということがあります．
〆切などのノルマを与えられた時に義務的に作業をこなすことはわりとできるようになったと思うのですが，自分から能動的には何もできないし，する気も起きないことが多々あります．
ぼーっとする時間も人生の中では大事だと思うのですが，そればかりでは，その時間でできるはずだったことをフイにしてしまっていると思います．
休息時間をちゃんと作るという意味でも，「時間はコスト」という意識をもっと強く持って，短時間で多くのことをこなすことが大事になると思います．
Pythonでダイクストラアルゴリズムを実装した
しばらく忙しくて，更新が途絶えてしまいました．
少なくとも今年度中は，2週間に1回更新を続けていきたいです．
本題．
競技プログラミングで，ダイクストラアルゴリズムを実装する機会があったので，ソースコードを載せておきます．
ダイクストラアルゴリズムとは？
ダイクストラアルゴリズム(ダイクストラ法)とは，重み付きグラフの探索アルゴリズムの一種で，すべての辺の重みが非負なグラフの単一始点最短経路問題を解くためのアルゴリズムです．
グラフの始点が与えられた時，そこから他の(すべての)頂点までの最短経路と，そこまでの重みの和(最短距離)を求めることができます．
ナイーブなダイクストラアルゴリズムはO(|V|^2)ですが，プライオリティキュー(優先度付きキュー)と呼ばれるデータ構造を用いることで，O(|E|log|V|)程度で最短経路を求められます．
Pythonでプライオリティキューを実装する際には，heapqというモジュールを用いるのが一番良さそうです．
8.4. heapq — ヒープキューアルゴリズム — Python 2.7ja1 documentation
以下，使い方．
>>> import heapq >>> q = [] # プライオリティキュー >>> heapq.heappush(q, 1) # 1をpush >>> q [1] >>> heapq.heappush(q, 2) # 2をpush >>> q [1, 2] # 1より2の方が優先度が低いので先頭以外に追加される >>> heapq.heappush(q, 0) # 0をpush >>> q [0, 2, 1] # 0の優先度が最も高いので先頭に追加される >>> heapq.heappop(q) 0 >>> q [1, 2]
常に，先頭に最小(優先度最高)の要素が来るようになっています(それ以外の順序は保証されません)．
ヒープを用いてインデックスを管理しているため，要素の追加，削除などの操作をO(log n)で行えるのが特徴です．
また，下記のように，Pythonでは，タプルを比較する時に，最初の要素から順に比較して大小を判定するらしいです．
今回は，プライオリティキューの優先度の計算にその性質を使っています．
>>> (1, 1) < (1, 2) True >>> (1, 1) < (0, 2) False >>> import heapq >>> q = [] >>> heapq.heappush(q, (1, 1)) # (1, 1)をpush >>> q [(1, 1)] >>> heapq.heappush(q, (0, 2)) # (0, 2)をpush [(0, 2), (1, 1)] # (0, 2)の優先度が最も高いので先頭に追加される
実装
競技プログラミング用のライブラリにしたいということもあり，無駄な処理はなるべく省くようにしたつもりです．
また，これは，グラフの表現方法として隣接行列を用いた時の解法です．
隣接リストを用いると，少しコードが変わると思います．
参考
![プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?](http://ecx.images-amazon.com/images/I/41bHxtpurqL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?")
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 473回
- この商品を含むブログ (33件) を見る
CODE THANKS FESTIVAL A日程に参加してきました
12/7(日)に東京で行われた，リクルートホールディングス社主催のプログラミングコンテストであるCODE THANKS FESTIVALのA日程に参加してきました．
この大会は，先日行われた別のプロコンであるCODE FESTIVALの予選を通過できなかった人に向けて，より多くの人に大会に参加してもらいたいというリクルート社側のご厚意により開催されたものでした*1．
自分は予選で，あと一歩の所で本戦参加を逃してしまったので，大会参加できることは純粋に嬉しかったです．
何してたかだけまとめときたいと思います．
コンテスト前
5時半起きで当日入り．
寒さが厳しかった．
受付を済ませた後に即昼食が出た．
叙々苑の焼肉弁当だった(めっちゃうまかった)．
昼食を食べながら，隣の人と話す．
年齢層的に大学1，2回生が多そうで，若干場違い感．
WebDB Forumの昼食会でお会いしたリクルートの人事の方に(2週間ぶりに)再会する．
「前回は服装ちゃんとしてたのに…」って言われた(笑)
ルール説明にchokudaiさんが登場．
初めてお会いしたけど，わりとイメージ通りの人で安心した(？)
コンテストとsubmitした解答
問題はすべてPythonで解いた．
事前に聞いていたように，いつもの大会よりは難易度易しめだったと思う*2．
A問題
与えられた入力値a，bに対して，4 * a + 2 * bを返す．
First Accept狙ったけど，同時開催されてたオープンコンテストの方にsubmitしてしまった*3．
B問題
A，B，Cを生産量の降順にソートし，順番に使っていくと最小の時間で処理が終了する．
C問題
S_iの値に応じて，P_iの値を足していく．
インデックスが微妙にズレてるのだけが注意点．
D問題
区間[s, t]と[a, b]の差を求めて100をかける．
場合分けしてしまったが，後で解説を聞いて，区間の共通部分はmax(0, min(t, b) - max(s, a))で求められることを知って悶えた．
この辺から手が止まり出す．
E問題
最初，問題の意味が解読できなかったので，先にF問題を解いて戻ってきた．
少し考えなおして，N回試行した後に各々の手順の分戻せばよいと気づくが，それでもO(RCN)=O(50*50*5000)となり，「Pythonだとギリギリだなー，もっと良い解法ないかなー」と20分ぐらい悩む．
でも特に思いつかなかったのでsubmitしてみると通った．
F問題
与えられた情報から，確定している順位の最上位を求めるとよい．
DFSを使っても良いが，N<=50なので，情報を何度もなめて，参加者1より上位の参加者を新たに追加できなくなるまで追加し続ける手法でもO(N^2)で十分間に合う．
ここまではすべて一発Accept．
G問題
手が出なかった．
少なくともブルートフォースのシミュレートで部分点ぐらいは取りたかったが，意外に場合分けが面倒だった．
想定解は，DPで，「何番目の人を見ているか」，「すでに着席している中で，最も番号の大きい人から番号の小さい側にいくつ空席があるか」，「すでに着席している中で，最も番号の大きい人の座標」を保存する手法らしい．
これは後で復習したい．
H問題
見た感じ，自分には手に負えない問題だと感じた*4．
Hに取り掛かった時点で残り1時間ぐらいだった．
順位表を見てみると，13位ぐらいだったので，部分点を通すだけでも入賞できそうだと思い，そこに注力した．
書いたコードがこれ↓
O(R^3C^3)という糞コード．
5分ぐらいジャッジ結果が返ってこなくて焦ったが，無事15点は取れた．
想定解は，中心の座標を決定し，そこから生地の左端までの長方形を考え，点対称となるかどうかを見ていくらしい(？)*5．
結果
615点で9位入賞．
正直，こんなので入賞してしまって申し訳ない感じはあるが，嬉しかった*6．
オープンコンテストの方で見ても45位ぐらいだったので，自分にしては上出来だったのでは．
懇親会
立食形式での懇親会だった*7．
DDRや太鼓の達人が置いてあった．
chokudaiさんめっちゃ頑張ってた．
個人的には書道コーディングが面白かった．
これは，普段コンピュータで行うコーディングを，筆で行うというもの．
結構いろんなネタがあった*8．
自分が書いたのがこれ↓
上でも書いたように，大学の学部生が多かったように思う．
般教の話とか久しぶりにした．
また，今回たまたまなのかもしれないが，女子率も結構高かった．
「プロコン」というと，どうしても男所帯のイメージがあるが，裾野を見るとそうでもないのかなと思った．
食事も豪華で，自分は寿司ばかり食べていた．
自分にとってはたぶん，学生生活最後のオンサイトのプログラミングコンテストになるかと思います*9．
本戦出場できなかった時は悔しかったですが，そこそこの結果を残せてよかったのではないかと思います．
そろそろ修論に取り掛かるべき時期が来てしまいました．
何とか修了できるように頑張ります．
