第25回高専プロコン競技部門参加記

今さらですが書こうと思います.解法についての詳細は↓

http://www.slideshare.net/opuctplab/h25-40607479

第25回高専プロコン競技部門,府立大学高専で優勝しました.

メンバーは@refiute @kagasantwi @kyuridenamida,そしてコーチ役OBの@mecha_g3です(雑用してくれた後輩もいました).

@mecha_g3には開発において,アドバイスをいろいろもらったりめちゃくちゃ助かりました.彼のおかげと言っても過言ではないし,感謝しても感謝したりません.

書き忘れていましたが同時開催というか,NAPROCKという国際大会があって,一般大学も含んで一緒に全く同じ競技をしていて,それにおいては東大に負け2位でした.

東大に負けてしまいましたが,決勝があのサイズだったからギリギリ負けただけで,16x16だったら圧倒的に負けていたと思います.悔しいですが悔しいと思ってもとらぬ狸の皮算用みたいなもんです.

4月当初

うわICPCとプロコン被ってる,ということでICPCとプロコンにメールを送ったがさすがに対応はしてくれなさそう.高専プロコン5年皆勤したかったので,ICPC犠牲にする代わりに今年は勝とうと思う.

怪しいパーサーとソルバを作って放置.

4月~7月

受験

8月頭

受験の疲れで何もしてない

8月末

そろそろスライドパズルやんなきゃと思うけど適当な考察ばっかしてた

受験終わってなぜか英語の勉強とかしてた

9月中旬

そろそろ動かないとやばい,とりあえず画像ジグソーパズルソルバーの論文漁ろうみたいな気分になる

英語論文ゲッチュ,refiuteとkagasanを巻き込んで受験勉強の一環みたいなノリで全訳作業に当たる.そのときmecha_g3とかも手伝ってくれるビビる.

中間論文を書いていて血を吐いている

kagasanが復元可能判定のルーチンをささっと書いてくれたのでそれを組み込む.


9月下旬

愚直ソルバを作りなおす.どんなサイズでも多項式時間で解けるようになる

ビジュアライザとか作る.眺める.

愚直ソルバに少しダイクストラを用いたら劇的に改善する

画像パーサとかが形になる

定期的にミーティングする

中間論文を書いていて血を吐いている

10月上旬

スライドパズル議論の末いろいろ思いつく

ななめに埋めてみたりする

議論で,テーブル使う手法が上がっていたが実装が重いので後回し

適当なダイクストラを真面目にミーティングで議論したら,劇的に改善(ビビる)

中間論文発表死ぬ

10月中旬

改善なし,コンテスト直前,死ぬ

そろそろ複数手を用いた改善とかをミーティングする.

本番用GUIがすごくなっている

中間論文発表死ぬ死ぬ死ぬ

コンテスト前々日

徹夜で学校さぼってひたすら1日中テーブルを用いるソース書く(ただし放課後は学校にいって中間論文書く)

コンテスト前日朝

またも連続徹夜で夜から朝にかけてコード書いた後家を出発

コンテスト前日昼

指導教員が引率教員だったので,論文添削してもらいながら飛行機乗る

コンテスト前日夜

論文修正しながらテーブルのやつのバグ取りする

中間論文締め切り1分前くらいに提出完了

本番用GUIが超すごくなっている

めしくう

うおーーーーと開発している.

GUIがよい.人の手で改善できるGUIすばらしい.

refiuteくんがweb競技システムを完成させてくれて,仮想テストができる用になる(あれこの日だっけうろ覚え).


コンテスト一日目(予行演習と一回戦)

まーた徹夜した気がする

テーブル使うやつでしょぼいソースが出来上がる.割と少しよい.

でも少しテーブルが弱くて本番で使えない.

競技場でぜんぜん勝てないしまっっっっっったく自信がなかったので各方面に自信がないと主張しておく

予行演習

潜伏のために変な数字でゴールインしようと思ったが,眠たくてろくに実装できず諦め.

でも潜伏したいので適当にダイクストラの評価関数を逆にした最悪コードで戦う(提出チェックができればよいので)

「なんで1位なんだふざけるな」

お昼休み

爆速でホテルに戻って眠たさと闘いながら変な数値を出すコードを書く

そもそも一回戦は3位になると東大と準決勝で避けれて嬉しいということがわかっていたので,1回戦1試合目は予行演習みたいに提出テストだった.

一回戦

1回戦は,3試合ある.

1試合目ちゃんとプログラムが動作し変な数値になる.復元もできていてハッピー.

2試合目はまともなプログラムを出して1位やったね.

終わった後僕とmecha_g3だけすぐホテル戻る

引率教員とかrefiuteが金色堂にいって,kagasanは自由部門とかを眺めていて,もうひとり助っ人後輩は会場で残りの試合を眺めていてくれた.

ツイッターみたらさっきの変な値に対して妨害かもしれないみたいな意見が見えて「あれで妨害になるようなポンコツシステムではさすがにないだろう」みたいな気分になる.

僕は眠いけどとりあえずいろいろテーブルのソースをがんばる.

少し寝た(2時間くらい)

一回戦の日の夜

やはり先の2時間以外ろくに寝てない,徹夜っぽい.

試合結果見て,仮想的に第一回戦の各高専と戦う.

「あれ,東大にはギリギリ負けているけどソレ以外の高専に普通に勝っている.いい感じでは.」

みたいな気分になる.

GUIがさらに進化したりする.

テーブルを必死に自宅のパソコンに計算させたり手元で計算したりする.何時間もかかる.

で,テーブルを使ってdpしたりいろいろするがうまくいかない

結局時間かけて生成したあるテーブルを使うと解が改善するということが分かりそれを使おうと思う

準決勝の朝

死にかけているけど開発続ける

準決勝

1試合目,いろいろな解法を投げまくる

複数選択強制だったのでしない解法のほうが解がめっちゃよかったんだけどあとのほうで実行したせいで,時間コストがあれで更新されない.

しかも交換手数893とかいう奇跡的な感じで,めっちゃ出したかったけどダメだった.

1試合目1位で通過やったぜ.

準決勝→決勝の間

悪あがく.少し解の良いプログラムが降ってくる.

決勝試合開始直前

東大横,ウィッス.

決勝試合開始直後

うわ問題サイズちっさ,とりあえず復元

とりあえず計算はやいやつ出す.割と良い解.

そのあとちょっと時間くらいかかるやつ走らせる.タイムペナあるけどスコア更新だ.

東大と競り合ってる 勝てそうかなあ勝てそうかな

負けた

くやしみ

決勝試合中

まったり

決勝直後

悔しいけど嬉しい.高専プロコンは優勝なので,校長顕彰(図書券1000円もらえる)を5年皆勤できたわやったみたいな気持ちになる.最後の年だし5年前に憧れてた先輩と同じ感じだし嬉しい.

でもやっぱ東大に負けたの悔しい.冒頭でも書いたけど16x16でなかったから競り合えたとは思っていて,16x16だったらアレだったのかも.


表彰

横に沖縄の人

眠すぎて番が来るまで寝る.ほとんど記憶にない.

インタビューも記憶にない.

なぜかなんかこころにぽっかり穴が空いている.

そのあと

バスで仙台まで乗る.

久留米の人たちにクソ絡みされる.眠すぎてマトモに応答できないすみません.

牛タン食って,めっちゃねるほんと幸せ幸せ幸せ幸せ

観光

青葉城とか行く.なかなかたのしい

コンテスト数日後

優勝したのがうれしくなる

感想

休憩時間に色んな人と話した記憶はあって半分くらい覚えてたり覚えてなかったり.

結局画像全部一発で復元できてしまって人力GUIを使うところがなかったのが残念.

他の試合にあったイラストのやつだけは人力GUIを少し使わなければならなかったが,イラストがあったのはその試合だけだった.

あとあまりにも前後徹夜しすぎて全く交流を楽しむ余裕がなかったの,最後なのにもったいなかった.

決勝中に眠たさから何も考えずひたすら回数制限まで送信したのは今考えるとよくなかったなあ(送信したい人がいるのに).

反省している.

忘れないうちに書いておきました.

みんなありがとうございました.


なとりうむさんはすげえわ