ACM-ICPC Asia Tokyo Regional Contest 2014 参加記

こんにちは, kagamiz です.
2014/10/18 - 2014/10/20 に行われた ICPC アジア東京地区コンテストにチーム "Heart of Master" で参加しました.
チームメンバーは

• @kagamiz
• @li_saku
• @gawaki

です. だれも修士課程に所属していません.
この記事ではコンテスト当日(10/19) とその前後の話をちょっと書きます.

問題はこちらから, コンテスト全体の順位はこちらから見られます. うちの結果を取り出すとこんな感じ.

Team rank	University rank	Team	University	Solved	Time
18	14	Heart of Master	Okinawa National College of Technology	5	555

10 / 18 (土)

朝 4:50 に家を出発する. 死にそう.

そこから飛行機で移動して, 13:30 くらいにオリセンに到着する. そのまま practice が始まる.

practice で皆で 1 回ずつ全問を解こうと思っていたら, DOMJudge では AC した後に問題に submit することが認められていないらしくて萎え (bits/stdc++.h がインクルード出来るか確かめそびれた).

その後は適当に Java Challenge を CPP でチャレンジする. たのし～.

その後懇親会. You and JAVA のチーム紹介がめちゃめちゃおもしろかった. 懇親会では久々に rox さんやよすぽくんに会う. あと 3 年越しくらいでショラーさんと初対面. Mi_Sawa さんとか math さん, iwiwi 先生に挨拶もできて大満足.

1 日めはそんな感じで寝る.

10 / 19 (日)

コンテスト開始前

rox さんとよすぽくん, ショラーさんと朝ごはんを食べてから会場に. さすがに緊張してくる.
会場到着後に FCCPC の皆さんと軽く挨拶をした. すたっきゅんさんに橋と関節点の記事を読んでもらっていた (実はこの後のコンテストで橋を求めるということをしたので, 解いているときにびっくりしていた).

コンテスト中

0:00 コンテスト開始

はじめに gawaki 先輩に A ~ E のサンプルをダウンロードしてもらっているうちに saku 先輩に A を読んでもらい, ぼくが B を読む.

A の概要を伝えてもらったが, ぼくが解釈をミスしてしまい $2^{n - 1}$ の変な全探索みたいなものを書き出してしまう. サンプルは合わない.
冷静に考えてソートっぽくすれば良い事に気づいて修正. 細かいミスをしていてだいぶ時間を食う.
サンプルがあったので提出

0:26 A AC

イェイ! 3 人でハイタッチ.

だいぶ A で手間取ってしまった. 僕の実装中に saku 先輩が C の解法を考えていたが, 考えていた解法でサンプルが通らないらしい. B は簡単な構文解析をすれば良いということを saku 先輩に伝え, gawaki 先輩には D を読んでもらう.
僕が C を読んで解き方を考える間に saku 先輩に B を書いてもらう.

C の解き方まで考えたところで先輩の実装を見守る. なんか実装は良さそうだけどサンプルが通らない. うーんと悩んでいたら

int ret = 0;
for (int i = 0; i < st.size(); i++){
    ret += st.top(); st.pop();
}

というコードがあるところを発見！Ω＼ζ°)ﾁｰﾝ. 修正してサンプルを通す.

0:50 B AC

よしゃ. ハイタッチをして次の行動を決める.

gawaki 先輩によると D はやばそうな幾何らしい？でもパッと見た感じ式が沢山載っていて丁寧そう. とりあえず C を解くことにする.
他のチームがぼちぼち F を解き出しているので, ぼくが C を解いている間に saku 先輩に F, gawaki 先輩に E を読んでもらう.

C はすんなりかけたとおもいきやバグを潜ませてしまう. しかし比較的すぐ直せた. サンプルも通ったので提出.

1:06 C AC

3 問正解！ ハイタッチ！！ 自分の中での目標は達成できたので嬉しかったが, まだまだ時間があるので頑張る.

saku 先輩「F は MST の中で必ず使わないといけない辺を求める問題らしい」
kagamiz 「それこどふぉで見たことあります( ｰ`дｰ´)」

ということで制約を見ずに F を解き出す. これめんどくさかったな～という思い出とともにひたすら書いたコードを思い出す. つらい. つらい.
サンプルが通ったので提出する.

?:?? F WA

えー... って気分になる. しかしよく見るとグラフの辺の追加でバグらせていたのでそこを修正.

2:16 F AC

チームメイトと喜び合う. コンテストの半分の時間でここまで解けるとは思っていなかったので嬉しい(残り半分で同じだけ解けるというわけではないけども).
みんなで一回リフレッシュルームに行く. practice のときよりめちゃめちゃ置いているものが豪華だった.

帰ってきた後に, saku 先輩に G の概要を教えてもらう. 最も左の位置って二分探索っぽいなあ～, クエリあたり $O(\log n)$ くらいの処理時間ってめちゃめちゃセグメント木っぽいなあという気分になる.

僕が F をこじらせている間にも E の AC が一向に増えないので E は捨てることに. ということで D に取り組むことにして, saku 先輩には G を考えてもらう.

D はああでもないこうでもないと唸っているうちに, $v = \sqrt{v_x^2 + v_y^2}$ から $v^2 = v_x^2 + v_y^2$, 幅 $w = 2v_xv_y$ から $v_x + v_y = \sqrt{v^2 + w}$ が分かり, またある $v$ でバウンドに成功させれば高さ方向にのみ$v+\alpha(\alpha > 0)$ の$\alpha$ を寄与させることが出来ることが分かり, 二分探索が出来る事に気づく. めっちゃコードをバグらせたが, サンプルがあったので提出.

?:?? D WA

サンプルは通ってるのに... という気分になる. 二分探索が収束していないのかなあと思い探索の回数を 10 倍にして, 速度の上界と下界をもう少し吟味した上で再提出.

4:00 D AC

なんとか D を通し 5 完！感極まる.

残りの時間で 1 問解きたくなる. G は Starry Sky 木を使って区間加算と加算後に正しい括弧の対応がとれているかのチェックをできれば OK そうで, 変更する位置については二分探索ができそう.
しかし, Starry Sky 木の実装法を忘れてしまい(!), 残りの 60 分を Starry Sky 木のデバッグに潰す. 解説記事 を書いたはずなのに... 解けなかったことよりショックかもしれない()

5:00 コンテスト終了

順位表を見た感じ 18 位？ 下の方に抜かれないように祈って問題解説を受けに.

コンテスト後

G の解法の方針はあっていたらしい. そもそも Starry Sky 木をかけていないのでダメですね...
E はなんか解けそうな問題に見えていた. もっと分担を考えないといけないなあと思った.
あと D の解説が解説じゃなかった気がする(コーナーケースにこんなのがあったよ, みたいな紹介っぽかった)

そのあとは Java Challenge を見る. なぜか決勝に進出したが, 決勝では 3 位タイ. (実はその後に再戦があったらしく, 負けたので 4 位でした.)

結果発表では 6 完から登壇していた. もう一歩, という感じだった.

Closing Party では hyksm さんと rox さんと一緒にいろんな企業のブースを回ったり, 話をしたりした. そすうさんがおでこに JAG シールを貼って引退と言いまくっていた.

最後に, いろんな人に ICPC シャツにサインを書いてもらった. 誰がどれを書いたのか当ててください.

写真つけ忘れてたw pic.twitter.com/EMLvPZIH39

— 榛葉(Shimba) (@kagamiz) 2014, 10月 19

10 / 20 (月)

7 : 00 起床. 7 : 30 にご飯を食べに行こうとしたが, よすぽくんが 7 : 30 に起きたので, 準備を見守っていたら 8 : 40 とかになっていた. ギリギリでご飯を食べて excursion へ.

excursion では Dream Arts, リクルート (Indeed Tokyo), LINE へ行きました. どこもノベルティが豪華だった.
前 2 つの会社ではお互いの意見交換みたいなものをする時間があって, そこでも交流ができてよかった.

話を聞いたり, 話をしたり, 移動したりでへとへとになって羽田空港につく(17:30 くらい). しかし翌日は学校で授業があるためまだまだ移動は終わらない(つらい).

22:30 に沖縄について, 24:30 くらいに学校の寮につく. ブログ書くかーと思ってベッドに寝っ転がっていたら朝だった.

まとめ

• ICPC に出たい欲が増幅した(出場回数制限があると思っていたけどそれは World Final に 2 回出場したときのことだった).
• 全体としてみるとほとんど僕がコーディングをしていた. というか作戦会議が少なかった. これは次に向けて反省しないといけない.
• F 問題は制約的にもっと楽な解き方があったので, ちゃんと制約を読もう.
• 競技プログラミングはとっても楽しいしこれからも続けていこうと思った.
• 交流をめちゃくちゃすることができた.
• 今後参加できる機運があれば, ノベルティ用バッグの用意を真剣に検討すべき.

スタッフのみなさん, 選手の皆さん, そしてチームメイトの先輩方とコーチにはとてもお世話になりました. Starry Sky 木は忘れても今回の経験は絶対に忘れません :).
来年は普通に予選を突破して, アジア地区大会で皆さんにお会いしたいです. そう出来るよう, 来年に向けて少しずつ動いていきたいです.