学生プログラマ日本一決定戦 CODE VS
CODE VS公式サイト【http://codevs.jp/index.html】
ここ1ヶ月ほど、こんなものに参加していました。
2011/12/1から2012/1/6までが予選期間で、その参加者のうちの上位8名（ただし学生のみをカウント）が決勝進出。
そこから2012/1/13までに決勝用のプログラムを書き上げ、2012/1/14に決勝参加者8名のコードを互いに闘わせます。個人戦のトーナメント形式。で、ベスト8とベスト4と準優勝と優勝が決まります。
このCODE VSは、マラソンマッチ風の長期戦型プログラミングコンテストであると同時に、「優れたプログラミング技術を持つ学生を発掘する」目的で、日本の（主にＩＴ系の）企業主導で行われた初めての大会でもあります。
予選に参加登録するときに「希望職種」とか訊かれますし。予選開始日に至っては12/1。なんて露骨
あと、決勝戦の日をセンター試験当日に被せてきたのは、形式的には学生全体を対象にしつつも、優秀な高校生は決勝の枠を食いつぶすのを防ぐ意味合いもあったのではないかと思いましたが邪推しすぎですかそうですか。
というわけで、自分がこの大会に出て何を考えて何をやったかについての簡単な報告記事です。
予選
予選ルール：【http://codevs.jp/common/data/codevs_rule.pdf】
とりあえず、前半の1〜40面は全ての敵出現マスの隣にレベル4ラピッドタワーを1〜2個建てれば、後半の41〜80面は適当にレベル0ラピッドタワーで迷路を作ったあと適当な個数レベル4ラピッドタワーに強化すればクリアできるので、全クリ自体は簡単。
埋め込み解を防ぐために生成される面はSubmitごとにランダムに変化する、なんてことが書いてありましたが、気にせず全クリコードを何度も送信して様子を見てみます。
与えられるステージや敵の入力データを収集、分析。
すると、敵に関する全データ、ステージのサイズ、全敵出現マスと全防衛マスの位置は常に固定であることが分かります。
また、毎回形を変えているマップも、よく見ると
22 18 //予選57面の例 ###################### #*...........#.g.....# #........*......#....# #....g.....*......*..# #...................## #.........#...*.#.*..# #g...................# #......*...*.........# #..........*.#...#...# #..#*............*.s.# #.#......#.#....#....# #..#...#.............# #.#s...........#.....# #.......#....#.......# #.........g.......#..# #....*..#g...*.......# #....................# ###################### //#は壁 .は床 *は壁または床のどちらかに変化
のように、ランダムに変わるとは言いつつも変わる地点の数はわりあい少数であることが分かります。
また、*が床に変化したときは、そこにタワーを建てれば壁とみなすことができます。
じゃあ手動で解けるじゃん目から鱗
というわけで、予選期間中はひたすら手作業で遊んでいました。
実際、ちゃんと動く完全自動タワー配置プログラムを組みあげた今となっても、大抵の場合において、自分のプログラムが出した解よりも優秀な解を手動で求めることができます。
これは人間が優秀だというより自分のアルゴリズム力がゴミクズなだけではないかとか思ったとしても言ってはいけない
もちろん、ハイスコアを目指すのであれば、手動とプログラムをうまく役割分担させることが必要なのですが、予選では学生の中で8位以内に入れれば十分なので、結局ほぼ手動だけで予選を乗り切ることに決めました。
より正確に言うと、とりあえず手動で遊んで様子を見ようと思って手を付けたら思いのほか楽しくて止められず気づいたら予選終了1日前だった
なお、自分の予選の成績である「総合4位、学生3位、スコア78952」は、手動で全力を尽くした結果かと言えばそういうわけでもなく、まだまだ手動だけで点を伸ばせる余地のある面が大量に残っています。
もし（時間がもっとあって）手動で行きつく所まで行っていたら、cos65535さんの103079に届くか届かないか、くらいの所までは行けていた気がします。
colunさんに宣戦布告しておきながら結局真っ向勝負しなかった自分は、Twitterリムられてブロックされても文句言えないレベル。
あ、あの……、本当にすみませんでした。
そういえば、この予選は優れたプログラミング技術を持つ学生を決勝に招待するのが目的だったはずなのに、釣れたのはただのヌルゲーマー。まあ仕方ない
というわけで、運営側に提出したコード類の中に堂々とshudo.txtが入っている偽アルゴリズマーは、ちゃっかり決勝へ。
決勝準備
決勝ルール：【http://codevs.jp/final_popup.html】
決勝戦は、マップや敵の入力データが予め与えられないという、予選とは打って変わってゲーマーお断りのルールで行われました。
ちなみに、決勝戦のルールが明かされてデモプログラムが配布されたのが1/9の20時。
ソースコードの提出締め切りであるリハーサルの開始時刻は1/13の14:30。
しかも1/11と1/12は何かと忙しいせいであまり開発時間がとれない。
予選のプログラムを流用しようにも大半の時間を費やしたのはshudo.txt。おいいいい詰んだ
仕方ないので、楽をします。
まず、「レベル0ラピッドタワーで迷路を築く」と「そのうち何個かをレベル4まで強化する」の2つの処理を分離して、独立に考えます。
手動でやっていた時には考えられない暴挙ですが、この両方を同時に最適化するアルゴリズムなんて難しくて思いつきません。もしくは実行時間がかかりすぎる。
最初のステップ。迷路作り。
とはいえ、まともに迷路を作るのは実装が大変なので、敵の進路を妨害するように塔を建てることを考えます。
具体的には、次のようにします。
まず、防衛マスを1つを残して上下左右を全封鎖。
そして、残った防衛マスまでの距離が最短な敵出現マスを選び、下図のように、敵が出現してから1歩先の場所に塔を建てます。建てられない場合は2歩先、3歩先、……と候補を後ろにずらしていきます。
これを、もう塔が建てられなくなるまで繰り返します。
実際にはいくつかの改良を加えていますが、基本はこれです。
これに若干のランダムを入れて何度も繰り返して、もっとも性能の良い迷路を選びます。
焼きなまし、というか、適当に点を選んでそこの値を調べているだけも同然の行為なので、手動の性能には到底およびません。山すら登ってねえし
ちなみに、迷路の評価は、敵出現マスから防衛マスまでの距離の最小値が大きいものを優れた迷路としました。
これも手動では考えられない酷い近似ですが、この最小値と迷路の良さにはかなり強い正の相関があるので、シンプルにこれを採用します。
でも、蓋を開けてみると、決勝に参加した8人が8人とも、自分の迷路に匹敵するまたは劣る迷路しか作れていなかった気がするので、手動が封じられると現実的にはこのあたりが限界という説はあります。
次のステップ。塔の強化。
こちらでは、最大強化にしたときの射程範囲内をなるべく長く敵が歩くようなラピッドタワーから順に最大強化していきます。
シミュレーションしながら、ノーダメージで敵を全滅させられるようになるまでこれを繰り返します。
フリーズタワーは先のレベルの状況が分からない決勝では使いづらいので放置します。
アタックタワーは元々いらない子なので無視します。
ここまで組むのに約5時間。
あとは、15時間ほどかけて、この両ステップを高速化することに心血を注ぎました。
元と等価なプログラムを保ったままでの高速化だけではなく、若干スコアが下がることを覚悟しての高速化や、たまに建てられない所に塔を建ててしまうけれど大抵の場合は大丈夫、みたいな高速化までやりました。
なにせ決勝は、相手よりも処理時間が1ms遅れるごとに1money減点されるルールなので、プログラムの高速化は非常に重要なのです。
1回1回の試行が速ければ、ランダムに試せる回数も増えて、良い迷路が見つかる可能性も上がりますし。
労力をかけた甲斐あって、結局、他の決勝参加者と比べて時間面で優位に立てるプログラムを組むことができました。
ただし、その代わり、ある重要な処理を組み込むことをすっかり忘れていました。
全ての塔を最大強化してもなお致死量のダメージを受ける場合は、フリーズタワーを使ったり、そのレベルに特化した迷路に新しく組みなおしたりして、金に糸目をつけずにライフを守る必要があります。
決勝のゲームバランスでは、30面を超えたあたりでちょっと狭いマップ（それなりの確率で出現する）が出るたびに、塔を最大強化しても足りなくなってしまいます。
なのに自分は、このことをすっかり忘れていました。
時間がなくて組めなかったと言うよりは、時間がなかったせいで、これを組む必要があるということがすっかり頭から抜け落ちていました。
そんな致命的な欠陥を抱えたプログラムを提出してしまったことに気づかぬまま、決勝本番へ。
決勝戦
決勝会場にて、CUTEGさんとPOPさんのイラスト入りクリアファイルをゲット。
これらは非売品で、これだけでCODE VSに参加した価値は十分にあったと言えます。
どのくらい十分かと言うとn<=300の単一始点最短路問題ならワーシャルフロイドで十分なくらいに十分
さて、いよいよ決勝トーナメントの開始です。
8人の参加者が箱の中（見えない）からボールを引いて、トーナメント表の位置を決めました。
まずはベスト4決定戦。どの闘いも、勝者と敗者のプログラムにはあからさまな性能差があり、8人のうち下位4人が順当に敗退したといった感じでした。
次にベスト2決定戦。どちらの闘いも、勝者と敗者のプログラムには有意な性能差があり、4人のうち下位2人が順当に敗退したといった感じでした。
これが起こるのって相当に珍しいですよね？
実力が同じ人物はいないと仮定して計算してみたところ、確率は約15.2%。
なんだそこまで珍しくもないのか。どっちだよ
あとまるで関係ないけど%の直後に句点をつけるとパーミルに見えるね。15.2‰とかレア
そして決勝戦の中の決勝戦、優勝とその他大勢を分ける最終決戦が始まります。
かたやjellies（自分）、かたやyuukiさん。
yuukiさんのプログラムのこれまでの闘いを見たところ、または本人から直接話を聞いたところによると、yuukiさんはどうやら真面目に迷路を作っている模様。
「敵が歩くルート上に塔を建てる！」というだけのワンアイデアで最後まで走りきった自分とは違い、敵が通るルートをベースに考えてアルゴリズムを固め、複数の敵出現マスの合流地点をプログラムで陽に制御したりとかまでしていたようです。なにそれ組める気がしない
さらにyuukiさんは、全ての塔を最大強化してもなお敵を全滅させられないときは、ラピッドタワーをフリーズタワーに変えたりレベルごとに迷路を組みかえたりするといった処理まできちんとプログラムに組み込んでいるようでした。そう、自分が完全に忘れてたアレです。
事実、ベスト2決定戦（どちらの闘いも同じマップを使って行われる）では、自分がライフ0になって死んだ非常に狭いマップの43面をyuukiさんはクリアしています。対策してないのとしているのを比べればさもありなん。プログラムの根本性能に差がありすぎます。
リアルに、CODE VS!!―正義の味方を倒すには状態。
はっどうせyuukiさんとか勝てるわけないのに皆ムキになっちゃって馬鹿じゃねーの
だがちょっと待ってほしい。
VSでは、悪の戦闘員はヒーローのうち1人を沈めることには成功したのではなかったか。
召喚された瞬間に負け確だとしても、ヒーローに変身カードを使わせる暇を与えずに、数の利を活かして攻め続ければいいのではなかろうか。
そう。 狭 い マ ッ プ が 出 現 し な い こ と を 祈 れ ば い い
必死に。
ラッキー・ストライプを３積みし、太陽を連想するカードを全て排除したデッキを胸に、いざ決勝の舞台へ。
と言ってもプレイヤーに出来ることはただ見てるだけなんだけどな。開発初期のポケモンみたい
ばとるスタート。
敵の進行を妨害する位置に塔を建てるだけというシンプルなアルゴリズムが功を奏したのか、それともRuntime Error死のリスクを覚悟で行ったプログラムの高速化（＆ソースの煩雑化）にかなりの時間を費やしたおかげか、自分のプログラムはyuukiさんのそれと比べて圧倒的に速いです。
決勝ルールにより、かかった時間の差分のお金が、1msあたり1money、yuukiさんの所持金からガリガリ削られていきます。
5000money差がつき、10000money差がつき、ほぼ1面分の資金差が開きます。
あとはこのまま、簡単な面が出続けてくれれば、順当に相手の資金切れで勝利できます。
だが・・・出るっ・・・！
40面を過ぎて・・・狭い面・・・！
瓦解。転落。焦燥。めのまえがまっしろになった！
なんせ、狭い面に対して相当の対策を施してきているyuukiさんと違い、自分のプログラムはただ塔を最大まで強化するだけです。
まさに敗色濃厚。圧倒的絶望感。いくらmoneyが残っていようと、相手より先に初期ライフ10がゼロになってしまえば何の意味もありません。
でも。
ここまでの不利が重なっておきながら逆転できないなんて、嘘だろう？
というわけで、ここで要素の相対論の神様降臨。
「まさか、
狭い面が終了した段階で、度重なる敵の猛攻を10あったライフを7も残して余裕でしのぎきったyuukiさんに対して、自分のライフは、残り1。
だがギリギリだろうと何だろうと耐えてしまえばこっちのもの。
あとは何面か簡単な面が淡々と続き、yuukiさんの資金が先に底を尽き、この闘いは自分の勝利で幕を閉じました。
生存戦略、外道上等。
決勝アフター
勝ったあああああああああいやっほうううううううううううう！
闘いの後は、表彰式だったりインタビューに答えたり懇親会だったり打ち上げだったり。
他の参加者たちの話を聞いて、新しい発見の数々に、目から鱗の連続でした。
具体的には、こんな感じ。
自分「自分の環境で動いていたプログラムが本番環境で動かなかったので、何がマズいのかと思ったらCygwin絡みのDLLが本番環境になかったのが原因でした。なのでソースとdllファイルを一緒に提出して動かしてるんですよー」
他の参加者「それ毎回DLLを読みに行くから遅いですよ。-mno-cygwinつけてコンパイルすると2倍くらい速くなりますよ」
何・・・だと・・・！？
自分「予選ではまず全クリできるプログラムを書き上げて、それを何度も提出して得られた入力データを統合することで、面や敵のデータを解析しました」
他の参加者「それデモの実行プログラムを逆コンパイルすると一瞬で入手できますよ。Javaだから簡単だし」
何・・・だと・・・！？
自分「他の人がどの面でmoneyをいくら消費しているのかの詳細なデータが欲しかったですね。あのmoneyの推移グラフは荒いので、1ドット単位で解析しても正確な値は得られない」
他の参加者「それデモプログラムとサーバーがやり取りしているデータを直接取得すれば普通に分かりますよ」
何・・・だと・・・！？
他の参加者「そもそもなんでcygwinで-O3なんて使ってるんですか？」
自分「いや……詳しいことは全然分からないんですけど……。普段アンダースコアーズで偉い人がそれでコンパイルしているので…………」
みたいな。
特に最初の会話、5時間かけてコードを煩雑にしてバグ混入の高いリスクを負ってまで迷路生成の速度を2倍にした自分の努力とは一体なんだったのか。
なんかもうね。自分だけ場違いな所に来ている感が甚だしかったね。
学生プログラマ日本一決定戦のはずなのに、なんでプログラムに詳しくない人が決勝に居んの？ 的な。
自分マジアウェー。
なにせ、懇親会で様々なスポンサーor主催企業の方とお話する機会があったのですが、その中で一番盛り上がった会話が、Pixivの方との
Pixiv「優勝おめでとうございます」
自分「ありがとうございます」
Pixiv「クリアファイルは受け取って頂けましたか？ あれ非売品なんですよ」
自分「はい。大切にします。CUTEGさんいろんな所で活躍してらっしゃいますよね」
Pixiv「そうですね。最近は講談社の出してるライトノベルとかでも」
自分「彼女がフラグをおられたら、面白いですよね。きれいな竹井10日先生とか新鮮で」
から始まる一連の会話だったくらい。
韓国の絵師さんをよく見るようになりましたよね、光の魔術師の方とかおいおいVOFANさんは台湾じゃねえかHAHAHA〜．的な。
これ絶対プログラマーの会話じゃねえ
さらにこの後の飲み会では、決勝参加者や運営側の人間が集まって、様々なトークに花を咲かせていました。
プログラマーの飲み会らしく、好きな言語とか、マニアックな言語仕様とか、最新の開発環境についてとか、各種IT系企業の良い所や不満とか、そういう話ばかり。
もちろん全然ついていけませんでしたが何か
学生プログラマ日本一だけが、2位〜8位の会話においてけぼり。
客観的に見るとすっごい面白い絵面なんだけどなんだこれ。
自分マジぼっち。ひとりがすきなボッチの、ともだちは、じぶんひとり
これは2期ＯＰで一人だけ（笑）とか付けられて紹介されるレベル。
もしくは自分のニックネームを募集したらショーキン☆ドロボーとか名付けられるレベル。
まあ別にこの疎外感は今に始まったことではないですけどね。古くは高3のときの情オリ合宿から。
というか、そういう場でプログラミング言語について語るのは、数学オリンピックのメダリストたちが自身の愛用する鉛筆の特徴について熱弁をふるっているようなものだと思うんですがまあこれ言っても誰も納得してくれんよね
ところで、こういう場で成果を残した競技プログラマーがインタビューを受けるときの鉄板回答に「競技プログラミングそのものは実務に直接役に立たないが、そこで培われた問題解決能力を、現実の様々な問題を解くのに役立てていきたいです」というものがあるんですが、自分はこの答えがあまり好きではありません。
別にこの考え方自体を否定しているわけではなく、というかこう考えている人のことは立派だと思いますが、競技プログラミングというものにまず実務への応用ありきみたいなイメージがついてしまうのがなんとなく嫌なのです。
というわけで、これとはまた違った、しかし独り善がりにならず対外的なイメージも悪くない、競技プログラミングの魅力を新たなベクトルからアピールするような回答を用意していたのですがいざＮＨＫにマイクを向けられると↑の鉄板回答を一字一句違わずに答えていた
まあＮＨＫだからね。仕方ないね。
自分のような社会的弱者は長い者に巻かれておくのが基本
それとあれだ。とある参加者が「この3日間寝てない」とか言ってて、企業の方からも「皆さん頑張って徹夜で開発されてきたことでしょう」みたいなコメントがあり、寝ないのが当然みたいな雰囲気になっていたので、自分も「昨日は寝てません」と言っておいたのですが、実は8時間くらい寝てた。うわっ私の睡眠時間長すぎ
よく「寝ないで働いている人は有能」だったり、逆に「働きながらもちゃんと寝ている人は有能」だったり言われますが、作業効率の良さと寝ないでも作業できる能力の2つは別物なので、注意が必要です。
まあ自分は両方ないんだが
あと、インタビューで「優勝できた理由は？」みたいなことを何度か訊かれたので、その答えを重要な順に書いておくと、
（１）wataさんがCODE VSに興味を持たなかったこと
（２）chokudaiさんが運営側に回ったこと
（３）colunさんが学生ではなかったこと
あたりが主要因。
ちなみにインタビューでは（２４）〜（２６）あたりの理由を答えておきました。
それでも、yuukiさんは相当に手強い相手だったのですが、これに勝てた理由は、カブトボーグ的に言うならば9話で勝治が石田母に勝てたのと全く同じ理由。
うん！
まとめ
予選：ゲームやってた
↓
決勝準備：手抜き
↓
決勝：運
↓
アフター：ぼっち
まとめてみると想像以上にひどい
事実、他の参加者からは、言語設計の根底に流れる思想だとか説明会では聞けない企業の裏話だとか色々と有用な話を聞かせてもらった一方で、自分が他の人に与えられた知識はと言えば、「CUTEG」は
おい本当になんで参加したんだよこいつ
まあしかし、えてして世の中は不条理なもので、自分が「学生プログラマ日本一」の称号を獲得したのは事実。
そこで今度、競技プログラミング漫画が出版される暁には、是非とも自分をモデルにしたキャラクターを出演させて頂きたい。
具体的には、第１話で、「この方は学生プログラマ日本一のjelliesさんだぞ！」とか取り巻きに言われながら目障りな主人公に勝負を挑んで瞬殺される役回り。
ファイブレインで言うところの武田ナオキのポジション。
せめてそこはジーニアス奥寺くらいの立ち位置になりませんかね
CODE VSへの意見
こうした大会が開かれるのは初めてなのでノウハウが無かっただろうことや、chokudaiさんが参加するまで運営側に競技プログラマーとして優秀な人材がいなかったことなどもあり、この大会について参加者として不満を感じる点は多々ありました。
ですが、最終的には、決勝トーナメントは盛り上がりに盛り上がり、こうした競技に多少なりとも興味のある人ならば楽しめる大会になっていたと思います。私自身も非常に楽しめました。
また、競技プログラミングを幅広い層に広めるためにも、この大会は一役買えていたと思います。
運営側のみなさん、他の参加者のみなさん、本当にありがとうございました。
ただし最後に1つだけ。
決勝進出者が運営側に提出したソースコードを、企業の方にレビューさせるとか自殺行為以外の何物でもない
おわり。（就活と言い張ってタワーディフェンスばっかりやっていられた日々が）
（※本記事には、話を分かりやすくするため、若干の嘘と誇張や厳密でない表現が含まれている場合があります）
