どうも、chop.chopです。

昨日無事に院試を終え地元に帰ってきました。

手応えとしては十分で、試験終了直後は9割くらいとれている自信がありましたが、東京特有のオシャンティーな喫茶店で自己採点した所8割くらいに落ち着きました。
案外解き直してみるとミスが多かったりするもんですねぇ……開始直後に錯乱して初歩レベルの積分を間違えたと気づいたときには脱糞しそうにナリました(あああああああああああああああああああああああああああああああ！！！！！！！！！！！(ﾌﾞﾘﾌﾞﾘﾌﾞﾘﾌﾞﾘｭﾘｭﾘｭﾘｭﾘｭﾘｭ！！！！！！ﾌﾞﾂﾁﾁﾌﾞﾌﾞﾌﾞﾁﾁﾁﾁﾌﾞﾘﾘｲﾘﾌﾞﾌﾞﾌﾞﾌﾞｩｩｩｩｯｯｯ！！！！！！！ )。どうか皆さん試験中は常に冷静に。

さてそれでも数学は記述方法だったりちょっとした所だったり不安な点が多いので、今朝自大で仲の良い数学科の先生に採点してもらったところ、

解析学:67点
線形代数学:80点

になったので、数学はそこそこと言った感じ。

残り２つが選択科目で、情報系の私はもちろんアルゴリズムとオートマトンを選択(信号処理とアーキテクチャも保険として解けるようにはしていましたがやはり苦手)しました。

アルゴリズム:100点
オートマトン:75点

やったぜ。
オートマトンは勉強したことが実を結んだという感じ。正規文法、文脈依存/自由文法に関する論述形式の問題、遷移図、NFA-DFA変換、チョムスキー変換、グライバッハ変換等が主な問題だったので解けるところは確実に点数がとれました。逆に一見して無理そうな問題は飛ばしてしまったので、部分点は望みようが無いですね……

さて、今回の大役者、アルゴリズム君は非常にいい仕事をしてくれました。
ここの院のアルゴリズムは競技プログラミングが得意な人なら解けるという傾向があります。逆に計算量やデータ構造に関する問題はそこまで出ていません。
今年のお題は、最長部分回文の動的計画法。

例えば、文字列:abbacaaの中で最長の部分回文は、bbとcを飛ばしてaacaaという文字列が回文として最長となっておりこれの長さは5です。これを動的に見つけるアルゴリズムに関する問題となります。

文字列の長さをnとすると、力任せな方法では、元の文字列によって部分的に生成可能な全ての文字列を逆方向から照合していって、回文となっていればその長さを記録して最大値を求めることで可能です。
これだと文字列の生成の時点で2^nかかり、さらにそれを元の文字列と照合し、回文に成り得る要素全てを書き出す必要があるので、各々の部分文字列が回文と成るうるのが高々1通りだとしても、一回に付きnかかってしまいます。O(n * 2^n)とかたまったもんじゃありません。

でもこの問題は簡単なアイディアでO(n^2)で解けたりします。発想としては単純で、注目している部分文字列を

α,h(1),h(2),...,h(l),β

のように表現したとき
α==β、のときならh(1),h(2),...,h(l)における最長の回文の長さ:sに2を足せばα,h(1),h(2),...,h(l),βにおける最長の回文の長さになります。
α!=β、ならα,h(1),h(2),...,h(l)における最長の回文の長さ、とh(1),h(2),...,h(l),βにおける最長の回文の長さ、の内大きい方をα,h(1),h(2),...,h(l),βにおける最長の回文の長さとします。

長さ1の部分文字列については常に自分自身が回文なので長さは1とすることが可能です。長さ2の部分文字列はn-1個存在し、現在の文字列のインデックスiを始点とする長さ2の部分列をiを一つづつずらしていき、i-1番目とi番目の文字が同じならその部分列の最長回文の長さは2、違うなら1とできます。
この後は上のアルゴリズムを逐次適用してやればO(n^2)で全体の最長回文の長さを発見できます。

正直アルゴリズムはもっと難しい問題を想定して他大学の問題を片っ端からといていたので少し拍子抜けでした。でも間違えようがない問題なので100点をとれている安心感はあります。アルゴリズムのいい点ですね。分かれば簡単。わからなければとことんわからない。

後は試験ではないですが、toeicのスコアを変換して点数として扱います。具体的にはmax(スコア/9,100)を点数として採用します。
私は700なので、700/9~77、77点を英語のスコアとして計上します。

最終的に全てのスコアを足し合わせると、
67+80+100+75+77=399
399/500~0.8

全体で8割とれました。これはウレシイですね…自大の教授によるとどこの院も6割前後をボーダーとされているようなので、余裕のよっちゃんです（白目）（9割以上狙うつもりだったなんて言えない…）。
落ちることはもうほぼ無いでしょうが、買って兜の緒を締めよということわざもあるくらいですので油断せず勉強しようと思います。

今回の院試で身についた習慣をこれからも続けることが出来るようにしなきゃ…（使命感）