こんにちは、碧黴(あおかび)です。
熱が冷めないうちにサクッとICPCの参加記をまとめようと思います。
チーム編成
チームAobayama_dropoutとして、こたつがめ(kotatsugame)とゆきのん(Yukly)の2人と組みました。結成当初、AtCoderレートは私が一番低く、足を引っ張るんじゃないかと心配でした。
戦略(4月〜本番直前)
4月の末くらいからICPCを見越した練習をはじめていこうと、AOJ-ICPCの問題を少しずつ埋めていました。出題される問題の傾向が普段のAtCoderなどのコンテストとはまるで別(実装がとても重いが、Cまでならハードなアルゴリズムの知識はそれほど要求されない)なので、この判断は正解でした。
結成したのが5月末くらいで、すぐにチーム練習に取り掛かりました。この時点では、具体的な戦略もなく、ただ漠然と過去問セットを埋めていくだけでした。そのため、2回やったチーム練習では2回とも3完で、結構不安になりました。
1週間前のJAG模擬国内予選の前に、軽く戦略を立てました。D、Eは一番レートの高いこたつがめに開始直後に投げ、2人でA〜Cを実装している間に考察してもらおう、というものです。後述しますが、本番ではこの戦略がバッチリハマりました。
JAG模擬国内の日、13時集合としたのに誰一人として図書館に到着しておらず、ガバガバ時間感覚なのが(主に人として)心配になりましたが、まあコンテスト開始に間に合えばいいかと思っていました。しかし……
こたつがめが “起きていない……”
前日の32時(つまり当日朝8時)に「ねね」と呟いたっきり音沙汰なしの彼のTwitterを見たときに感じた悪い予感は的中。結局、模擬国内は最初の2時間を2人で解きました。
セットとの相性が良かったこともあり、早いうちにABCEの4完、こたつがめが到着してからDをやりました。結局コンテスト時間内に詰めきれず、36位で終わりました。
模擬国内の参加者は本番の1/3程度で、さらに1問差で学内2位だったので、また焦りました。「全員起きれば勝てる」、そう心に言い聞かせ、残りの1週間を過ごしました。
戦略(本番当日)
1週間前に決めた通り、最初にD、Eをこたつがめに投げ、2人でA〜Cを解く戦略で行くことに決定。ゆきのんと私とでは得意な問題傾向が若干違ったので、(差別化する意味でも)構文解析や実装ゲーを私が、DPなどをゆきのんに担当してもらうことに。
昼過ぎに会場を提供していただいた研究室にお邪魔し、リハーサルセッションに参加しました。プリンターのチェックや4K27インチの人権モニターの設置も完了し、1時間程度そわそわしながら過ごしました。気持ちを落ち着ける意味でも、音ゲーのプレイ動画を見たり、「Eはやるだけ！(素振り)」していたみたいです。全員起床していたとはいえ、やっぱり不安でした。
そして本番スタート。冷房と緊張で冷え切った手ではうまくタイピング出来ず、マクロを打つのに結構な時間を食ってしまいました。その間にAを読んでもらっていたゆきのんにバトンタッチ、若干コケたみたいですが、とりあえずAC。後から知ったのですが、AのACはかなり遅いほうだったらしいです。
続いてB。折り紙の図が見えたので悪い予感がしたのですが、案の定だるい実装ゲー。要求されてる知識は簡単な幾何だけとはいえ、かなりバグらせやすそうな設定でした。折り目のindexに注目すればシンプルな実装にはなりましたが、サンプルの最後が合わない。折り返した紙がはみ出す場合もあるらしく、配列外サンショウウオしていたらしい。脳死で固定長配列を取り、サンプルがあったので提出。WA。えー
その間にCの考察を終えていたゆきのんにバトンタッチ。コードを書いてもらっている間に印刷したBのコードを読んでいましたが、バグの理由がよくわからず。Cを通すまでの間に、原因はわかりませんでした。
こたつがめが紙コーディングを終えていたようだったので、Dの実装を開始。ほぼ1発でサンプルを合わせ、あっという間にAC。強い。
さてあとはBをさっさと通せば時間的にもとりあえず35位くらいにはなれるか？というライン。紙で実装し直したのを書いても治らなかったので、出力をぐっと睨む。1440の文字。紙は最大で32×32=1024の厚みにしかならないので、明らかにおかしい。計算的に厚みを越えるような値にはなり得ないし、この値でオーバーフローも考えにくい……。
ここで、配列を固定長に取り直した際に初期化していなかったことが判明。ひどすぎる凡ミスだったが、あっけなくこれでAC。あなや。
この時点で学内トップ、30位ちょいくらい。あとは5完できれば予選突破を確実なものにできそうだったので、とりあえず残り4問に目を通してみる。Eは問題が読みづらい上制約がしんどい。とりあえずこたつがめに投げてみる。Fは幾何。うーん。Gは構文解析。試しにワチャワチャやってみるものの、どうも再帰下降で解けるタイプ(LL(1))ではなさそう。まあこの難易度だししゃーない。Hはこの時点で誰も通していないのでパス。
残り時間も限られてきたので、全員でEの考察をすることに。浮動小数点どうしの足し算の誤差を再現する、というもの。浮動小数点の仕様を理解するのに若干苦労したが、a+bという演算はa^b + (a&b)<<1 を再帰的に計算していけばできそう。これをダブリングっぽくやれば \(O(\log N)\) に落とせるか、と思いきや、誤差が再現されない。いろいろ考察してみてもダメ。結局残り30分ぐらいで愚直にやった際には誤差が再現されることが判明したものの、\(O(\log N)\) に落とすことはできず終了。あとから知ったのですが、誤差が生まれる計算の回数はたかだか50回程度らしく、そこまでまとめて計算することで解けたらしい。うーむ。
結果と反省
https://icpcsec.firebaseapp.com/standings/
4完40位(学内1位)。
- 全体の立ち回りとしては悪くなかった。結果的にDの早解きが勝因に。
- Aのsubmitが遅すぎた(4完以上63チームでワースト2位)。スコアが時間の和で取られることを考えると、マクロを使わないのも手か。
- 足を引っ張りかけたので、強みを作っておきたい。幾何とか。
一家に一台あるD-waveを持ち込めば10^18は気合で解けるんだよなあ
Asiaですっ転んでWAー！しないように精進しようね。おわり。
おまけ
Aobayama_dropout 邂逅ーーーーーーーーー pic.twitter.com/cbeNzYvZw7
— 碧黴(あおかび)@1日目西く-07b (@AokabiC) July 6, 2018