オンサイトのプログラミングコンテストへの参加はこれが初めてなので、うまく書けるか分かりませんが、頑張ってみます。
チームTECHNOのメンバー
・@shora_kujira16（TopCoderではarosh:緑）
・@kiri_5（TCはやってない）
・もう１名（ツイッター未利用、TCは同上）
- 1st_day
加古川ホームで集合 -> 三ノ宮で阪急乗り換え -> 十三 -> 石橋 -> 徒歩20分ほどで到着。
JMO*1したり領収書替わりの切符もらったりして、なんだかんだで3時間近くかかったorz。荷物（主にPC）重ぇ...
30分ほど余裕を持っていったつもりなのに、受付終了10:45分のところ10:35分頃サイバーメディアセンター到着。
誰にだったかは覚えてないけれど、席を案内される。
席には「H1T0HA」の文字が。／(^o^)＼ﾅﾝﾃｺｯﾀｲ。なんとしてでも顔を覚えてもらうぜ。
問題の概要が発表される。テトリスとぷよぷよの画面が表示されたとき参加者の間に戦慄が...
「なくろん」という落ち物ゲー（実は傾けゲー疑惑）を作成したので、そのスコアを最大化せよ、という問題らしい。（詳しくはSuperCon2011のページをご覧ください。）
最初見せられたのは8 * 8の盤面だったので、「あれ？全通り調べて終了じゃね？」 -> 250 * 250の盤面見せられて一同爆笑。
写真撮影と昼食後、問題の詳細とプログラミング環境について解説された。
なるほど、並列化はされなくて、ベクトル化というのをするのか。コンパイラ賢すぎﾜﾛﾀ。あとvim入っててうれしい！
15:00 〜 16:00までの強制休憩タイムでは、カントリーマアムが大人気。
「うわぁ、作ってきた名刺配れる雰囲気じゃねぇ...」 -> @nullmineral が配り始めてくれたので、有名JOIerたちの群れに一緒に突撃する。まどマギ名刺ケース大好評。*2 @kyuridenamida のいじられ方がTwitterのつぶやき通りで笑った。
本格的にプログラミング開始。とりあえず乱択TUEEEEEE! 適当に作ったテストケースでrandom:14000, greedy:14100とかで落胆。SX-8Rに3step_greedyのジョブだけ投げて、その日はrandomのソースをsubmit。
ホテルに着くと若干フォローが来ていた。就寝前に「ある方向に傾けたとき、落ちるボールの場所は一定」 -> 「傾けたときのスコアのみなら、割と高速に計算できる」ということを思いつく。最終的にくじら16号は、それをベクトル計算で高速に行えることなど全く気付かなかった。
- 2nd_day
前日の順位が発表された。FOYSOUNDがなんらかのバグにより出力できていなかったが、それを除けば最下位＼(^o^)／
前日の最後に投げたジョブの結果を見てみると、3step_greedy程度では効果が薄いことが発覚。考えたアルゴリズムがほとんど乱択解法に負ける呪いはこの時すでに始まっていた。
とりあえずスコアだけ計算する関数を作る。
壁10%のものは1000手、15%のものは2500手、20%のものは6000手ほどで99%のボールが穴に落ちることを実験により発見。
それをvisualizer.exe*3の画像で見ているとチューターの方が話しかけてきたのでその発見を伝えると、超ニヤニヤしていたので、「お？これは手がかりをつかんだかも？」と思ったが、「そういうわけで、とりあえずその30倍の30000回を上限にしてみたんだ^^僕は100000回を勧めてたんだけどね^^」というお答えをもらい、Failed System Test。*4
ところで、ご飯はほとんどCMC最寄りの食堂で食べた。味噌汁￥20は安い。
いくつかのチームが15000の壁を破り、焦り始める。いろいろな解法をつくってみるも、全滅。結局のところ、その日は「greedyにおいて得られるスコアが同点のものがある場合は、その中でちゃんと乱択する」というものをsubmit。（サンプルコードを真似して書くと、同点の場合 left > down > right > upの順に選ばれてしまうため。）
- 3rd_day
up と right に傾けたときに、どちらに転がしても穴に落ちる場所 == up に転がして落ちる場所と right に転がして落ちる場所の論理和、みたいなものを４つの角すべて調べることで、効率的に探索が行えるのでは？と考え、コードを書いてみる。壁10%のテストケースでしらべても、各角20個程度しかそんなマスはなく、午前中をほとんど無駄にする。
参加者用wikiの「ツブヤキ」コーナーに魔法少女ネタが流れ始める。*5朝から @semiexp 絶好調。スコアもツブヤキも実習室での発言も。*6
「著作権に触れるような書き込みなどは、冗談でもしないでください」という禁止事項欄に「しりとり」が追加されるチューター特権が発動されると、「山手線ゲーム！ => red coder」が開始。あとFizzBuzzで「6」って書いたのは自分です。
ちなみに @semiexp の「あー！！32GB取るとエラー出た！」という発言を聞いてチーム一同動揺。え...うちのチーム1GBも使わないんですが、一体どんな解法が？
ところで休憩時間にはjubeatやってる組と「バイオレンス・ノベル・ポーカー」というゲームをしている組があった。「魔獣鶴亀伝」がロイヤルストレートフラッシュらしい。「亀」の汎用性は異常。あと「女」というカードがその日のキーカードになるかと思われたが、相性のいい字が無く、邪魔にしかならなかったようだ。
@asi1024が誘ってくれたが、しばらくROMってた。うーん...参加しとけばよかったなぁ...
CMCのエレベーターは15人乗り。「いける！！いける！！」とかいって19人乗ってﾜﾛﾀ。*7
チューターの方々の中にvi使いの人がいて胸熱。
コーディングしながら、hakushinやVitaminKのところに「いかがですかー！！」と害活しに行きつつsubmit。
- 4th_day
トリッキーでゴリ押しなコードが完成。12:15ごろにsubmit。長くなるので最後に書きます。
自分のチームの解法などなどについてのインタビューが行われる。アンケートでは、特技："No such file or directory."の文字列でチューターを困らせること、と書いておいた。
ほかのチームと解法のネタばらし会。ほかのチームの解法に感動。
CMC本館のスパコン見学にはFateful, FOYSOUND, TECHNOが参加。
4面3D（名前がわからない...）を体験させてもらう。酔いそうなレベルの立体感で、3DS（笑）ってなる。*8
ホテルに18:30ごろ着いたので、このレポートの大部分を書く。
- 5th_day
7位。割と頑張ったんです。
チームTECHNOの解法について
人間の手でこのゲームを遊ぶ際には、その方向に傾けたときのスコアを見るのだけではなく、「落ちるボールのうち、どれだけが特典になるか」という割合（以下ではこれを「お得度」と呼ぶ）を考えているような気がしたので、このお得度 = 得点 / 落ちるボール を、その方向の評価値とした。
ただ、これを使って貪欲法でお得度の一番高い値を取っていくだけだと、時間を大幅に余らせてしまう。そういうわけで、この手法に乱数を導入した。[0,1)の乱数を生成し*9、それを利用してお得度の高いものが優先的に選ばれるようにする、という方法を壁10%のケースでは1000回、15%では2500回、20%では6000回行う。（この回数の理由は2nd_day参照）
上記の方法を時間いっぱい繰り返し、総得点が更新される操作パターンが見つかったら、その操作パターンを出力した。最後に出力されたものが正式な回答となる。
ほかのチームの発表を聞いていて思ったが、その「お得度」の値を２乗なり３乗なりしたほうが、差が大きく出ていい感じに選んでくれたのでは？と思った。
今大会の反省点
- 自分以外がCUI環境をほぼ全くと言っていいほど触ったことがない面子で、CUI操作を教えるのに丸１日を費やしてしまった。チューターの方々いろいろ聞きまくってごめんなさい...
- １名が3日目までずっと数学的解法的な物を考えていた。（３手目までの最適解が最速で見つかったとして、どう役に立つんだ...）明らかに自分のミーティング力不足。最適解なんて見つからないからスコアをできるだけ大きくする方法を考えるんだ、ということを理解したのが３日目夜になってから...
- ベクトル化がほとんどできなかった && メモリの多さを利用できなかった。先生方の話から"盤面の状態" or "今までの操作" のどちらかを大量に保存するのでは、ということを思いつくべき。
- 実 装 遅 す ぎ。要するにコーディングの経験がまだまだ足りてない。時間あるときにペアプロしてみようかな。
- もうオンサイトのコンテストに行けない可能性だってあるので、もうちょっと積極的に交流すべきだった。一応名刺はチューター含めて32枚配れたが... あ、Twitterのアイコンを印刷して名札に付けておくとみんな覚えてくれますよ！
- 精進
8/28追記 「傾けたときのスコアのみなら、割と高速に計算できる」について
私たちはsample_moveから単に遷移処理を除いた処理を書いていたのだが、ぱないがもっと頭のいい方法を考えていた。
破棄したコードがうまく使われていて衝撃を受けたので、一応書いておく。
まずmovable*10[4][SIZE][SIZE]を用意する。最初の[4]は、上下左右の方向、あとの[SIZE][SIZE]にボールの座標が入っている。
ここに予めボールが落ちる座標には1なり-1なりを入れてキャッシュしておけばよい。
この方法の利点は、ずばりベクトル計算を生かせることにある。
sample_moveからのコピペでもそれなりに早いのだが、
for(i = 0; i < SIZE; i++) { for(j = 0; j < SIZE; j++) { // 得点を計算する処理 } }
としたとき、得点を計算する処理にはif文なりwhile文なりが入ることになり、計算が独立しなくなるため、ベクトル化されるのは
for(i = 0; i < SIZE; i++) { // ↓ここから↓ for(j = 0; j < SIZE; j++) { // 得点を計算する処理 } // ↑ここまで↑ }
という結果になり、外側のループがベクトル化されない。
キャッシュしておけば、各計算が独立されるので、
// ↓ここから↓ for(i = 0; i < SIZE; i++) { for(j = 0; j < SIZE; j++) { // 得点を計算する処理 } } // ↑ここまで↑
がベクトル化される。
*1:Japanese Michimayoi Olympiad
*2:Twitterのプロフィールに「まどマギ名刺ケースの人」と付け加えておいた
*3:盤面の状態をpngにして出力するプログラム。参加者用wikiで全員にソースが配布された。
*4:と、このときは思っていたが、最終的にこれを大いに利用することになる。あとで聞いたところによると、PANAIの方々も利用していたようだ。
*5:『女装』の検索結果:22件
*6:うん、やっぱりアレな人だった！！！
*7:「もやし率高すぎだろｗ」と誰かが言っていたが、あながち間違っていない。
*9:乱数の大量生成にはベクトル化が行える専用の関数がある
*10:というよりfallableか？
