|
Nakachan+3というチームでICFPCに参加してました。
チームメンバは@kawatea03、@not_522、@pepsin_amylase、@simezi_tan、@wistery_k、@y3eadgbeです。強い（確信）
コンテスト中の様子
・１日目
コンテスト開始直前に某I研に集合。
コンテスト開始。問題文くっそ長い。
どうやらパックマンAIを書くらしい。ゴーストAIは追加来るなーみたいな話をする。
問題文をだいたい読み終えたのでamylaseさんに全体のシミュレータを任せる。
GCCのプロセッサをkawateaさんに任せる。このプロセッサは結局最後まで一度もエンバグしなかった。やばすぎ。
wisteryさんはゼミがあって寝不足だったらしいので先に寝てもらう。
GCCについてコンパイラ作る？どうする？みたいな話になる。
スタックマシンでtiny-Cを書くって課題がネットに転がっててコードの一部が公開されてたので、y3さんがそれでなんとかしようとする。
とりあえずGCCでタプルをスタックに積むコードを僕が書く。
y3さんがn回挫折した後、何とかなりそうとのことなので頑張って書いてもらう。
コンパイラが律速になってるけど、僕には分からない世界の話なので早めに寝る。
起きたらコンパイラもうちょっとでできそうみたいな話になってる。すごい。
朝食後y3さんが寝てsimeziさんとwisteryさんが配列とタプルの実装をしていた。
僕のやることが無くなってきたのでてきとうにビジュアライザをJavaで書く。半分寝ながらだったので３時間くらいかかった。
ついにコンパイラが完成したらしいのでいろいろ書いてみる。いろいろバグってる。
何とか書けそうだったのでAI書いてみたら途中でGCCのコードが消える謎バグに遭遇。
２時間くらい格闘した後、ネットに落ちてたコードが200命令までしか対応してないことが発覚…。
ギリギリ提出までいけるか？というところまで行ったけど、結局間に合わず、lightning divisionは正の点を取れなかった…。
・２日目
とりあえずAIのデバッグを進める。
lightning division終了後２時間でsampleクリアに到達。惜しかった…。
追加仕様は予想通りGHC。あまりに予想どおりなのでさらに追加が来るのかなぁとか考える。
とりあえずGCCからGHCを解釈するのは無理でしょという結論になる。
amylaseさんはシミュレータのGHC周りの実装、y3さんとwisteryさんがGCCコンパイラの修正、kawateaさんはTCOをしていた。simeziさんと僕は就寝。
（これ以降、コンテスト終了後まで僕はほとんど寝ていない）
起きてからビット演算を四則演算で処理できることを示したけど、やっぱりGCCからGHC読み込むのは非現実的だよなぁという話になる。
とりあえず生GHCを書いてみる。
if文くらい欲しいなぁと思ったのでインタプリタを書く。
while文とかrand関数とかも作る。
夕方ごろにkawateaさんが戻ってきてゴーストのAIを書いてくれる。
kawateaさんのコードを見ながらインタプリタを改良する。変数とか演算子とかを使えるようにする。
いつの間にかBASICもどきみたいなものが完成していた。
そのころ、コンパイラ係はGCCコンパイラのどうでもいい改良を行っていた。
simeziさん「GCCプリプロセッサ（を自作して）使えば？」
y3さん「（GNU C Compilerのプリプロセッサ使うのか。）しめじたん頭いい！」
というわけでdefineとかincludeとかできるようになって、repマクロが使えるようになった。どうでもいい。
コミットログ「bunmei no shouri」
まぁ２次元配列使えるようになったのはだいぶ楽になりました。
コミットログ「ninngennteki」
私物のプロジェクタを持ち込む。
https://twitter.com/pepsin_amylase/status/493392302589489152
ICFPC公式アカウントにRTされる。
※プロジェクタは壁に投影して使いました。
・３日目
kawateaさんが縦に動くAIと横に動くAIを混ぜれば良い感じに包囲できることを発見する。ゴーストAIはこれ以降細かい修正のみ。
とりあえずラムダマンもゴーストもだいたい満足できる状態になる。
ラムダマンがでかいマップの時に落ちるという問題を解消しなければならないことに気づく。
昼食後、他の５人が死んでいる横で周囲32×32マスだけを見る・１回のBFSで全部の処理をするように修正する。
後はひたすらAIの微調整。何故か自殺することがあったので無理やり修正したり、invisibleの処理をちゃんとやったり。
kawateaさんのゴーストAIが改良されて、ラムダマンがPowerPillの隣にいたらまだ取ってなくても逃げるようにしたり、PowerPill取っても残り時間を推定して食われそうにないなら迫るようになったりした。強い。
ラムダマンAIもBFS１回で処理してるとは思えないほど複雑な動きをし始めて知性を感じるとか言ってた。
コンパイラにSIMD的なものが実装されてマップの周囲４マスを１度に取れるようになる。
結局命令数はあんまり減らせなかったけどおそらく256×256でも動いてるだろうという結論になって、最終提出に向けて微調整をする。
READMEに2次元配列作ったとかSIMD作ったとか書いて提出。
kawateaさんのゴーストAIにamylaseさんとy3さんとkawateaさんが手動で挑んで全員負けたりしていた。
Twitter見てみんな配列作ったんだなーとか言いながら打ち上げして終わり。
感想
数年前からやってみたいなぁと思いつつ敷居が高くて参加できなかったのでけっこう嬉しかったです。
低レイヤの経験が全然ないので、コンパイラさくっと書けなくてすいませんとか地下勢頭おかしい…とか思ってました。
役割分担は
コンパイラ係：y3,simeji,wistery
シミュレータ：amylase
ラムダマンAI・GHCインタプリタ・ビジュアライザ：not
ゴーストAI・GCCプロセッサ：kawatea
と、そこそこいい感じになったと思います。（もうちょっとみんなAI書くべきだったかもしれない？）
lightningで正の点が取れなかったあたりはみんな意気消沈してたけど、結局それなりのAIができて楽しかったです。
来年も機会があれば参加しようかなぁ。
|
４年間参加してきたICPCを引退しました。
去年はWFを逃したり、今年は初の国内予選敗退で引退したり、悔しいことばかりでした。
去年はこんなに悔しいことがあるのかってくらい悔しくて帰りの飛行機で泣いてましたが、今年もそんな感じです。
悔しくて泣いたことはICPC以外ないし、WF行けなかったのはずっと引きずるんだろうなぁと思っています。
まぁしかし、そういう悔しい思いができたってのがICPCをやって得た一番の収穫でした。
自分の人生を振り返ってみると、勝てる勝負しかせず守りに入ってばかりで、本気で悔しい思いをすることはほとんどありませんでした。
台湾からの帰りの飛行機でチームメイトが寝てる横で自然と涙が溢れてきた時は、僕でもこんなに悔しいと思えるんだと、驚きすらありました。
きっといつかこの悔しい気持ちが自分の支えになることがあると思います。
最後になりましたが、ICPC関係者各位、特に一緒にチームを組んでくれたみなさん、本当にありがとうございました。
勝ちたかったなぁ…
|
競技プログラミングはじめた頃に「グラフ理論の用語わからんのじゃ」ってなった記憶があるのでまとめてみた
（まだ書いてる途中）
|
これは、Competitive Programming Advent Calendar Div2013の15日目の記事です。
注）pepsin_amylaseさんはコンテスト翌日に解説を完成させていました。
