ACM/ICPC 2011 国内予選 参加記？

早生まれのM2なので今年が最後の挑戦でした．

順位	チーム名	メンバー	A	B	C	D	E-G
20	Rokkaku	@shirokurostone @epee_noir @_shnyh	8:07	25:44	50:58	116:21(+1)	-

3時間前

実験室に移動して会場のセットアップ．机を大移動させたり，LANにつないだり，本並べたり．

1時間前

学内のコンビニに買い出しに行く．そこで別チームの@kioa341くんと@slip0110くんに遭遇．
微妙な空気になる．

30分前

15分前

30秒前

時計見ながらカウントダウン

開始

Aを@shirokurostone，Bを@epee_noirくん，Cを@_shnyhくんが担当．

A

@shirokurostone単独で担当．効率とか特に考えず愚直に実装してAC．

B

@epee_noirくんに問題の概要を教えてもらい，解法を二人で考える．
練習のときに似たような問題をやったせいで，そっちの方に引きずられて
解法を間違えて実装．サンプルが通らないので考え直し．
最終的に括弧を置換していけばええんちゃう？ってことに気付いて再実装．
無事AC．

C

@_shnyhくんに問題の概要を教えてもらって，これも解法を考える．
模擬予選のときにC問題の解法を間違えて時間を取られた事があったので
必要以上に計算量を警戒する．
が，結局幅優先以上の解法が思い浮かばなかったので実装開始．
え？計算量大丈夫？とか思ってたけど，サンプルが通ったので大丈夫だった．

D

@epee_noirくんと@_shnyhくんに概要を教えてもらい，
ホワイトボードに図を書きながら３人で考える．
円の上下関係を木で保存して(後々考えればグラフだった)，どう取り除いていくかの探索を考える．
これも練習の時に使ったbitDPが適用できる事がわかったので，実装開始．
サンプルは通った！よっしゃ提出だ！ -> bus error ( ﾟдﾟ)
gdbで落ちた箇所を調べてみると，DP用の配列に値を確保しているところ．
状態数分は確保しているはずなのになんでやーとか思って調べてみると，
何故か配列サイズが状態数(2^24)より小さい．
あってるはずなのにと思いながら計算した値(16777216)に変更し再挑戦．
(終わってから2^24を1024*1024*4と書いていたが，正しくは1024*1024*16という事に気付いた)
落ちる事なく終了したので提出．がWA．
また固まりかけたが，DP後の最大値を取得するループがおかしかったのを修正し，再チャレンジ．
今度はAC．ちょっともったいない事をした．

E, G

この時点で残り１時間．
また，解ける可能性のありそうなEに手をつける．
が，エリアの分割方法が上手く立たず，Gに移行．
幅優先探索と最短経路かと思ったけど，状態が爆発しそう&確信がなかったのでEに戻る．
この時点でもう時間がなかったので，方針が立たないまま実装を始めたがタイムオーバー．

終了後

Standingsを確認しアジア地区予選に出られることがわかり，一安心したところで，
超笑顔の@kioa341くんが飛び込んできました．

結果

うちの大学から初めて２チーム出場できる事になりました．
国内予選では大学内での潰し合い(で潰される)ことを本気で危惧していたので
両チームとも出られる結果になって本当に良かったです．

11月のアジア地区予選に向けて，頑張っていきたいと思います．