ICPC 2019 Asia Yokohama Regional参加記
2019年11月18日に横浜産貿ホールで開かれたICPC 2019 Asia Yokoama Regional 大会に、ziroppeくんとspiderさんとチームchoKOdaiとして参加しました。
結果はABの2完で、54/65位でした。予選最下位通過だったことを考えると健闘したと思います。ただ、もうあと一問くらい、Hは通したかった……。
準備
予選でABあたりの早解きを頑張って突破できた感じがあったので、それくらいの問題を一時間で解くみたいなバチャを立ててペアプロの練習をしたりしていました。チーム全員で集まって5時間フルの練習をするみたいなのは予定が合わず直前期にはできませんでしたが、9月中旬にあったJAGの夏合宿に参加させてもらって、むずかしーと言いながらも5時間コンの練習ができたのはよかったです。
1日目 11/16(土)
1日目はコンテストのリハーサルとチーム紹介などがありました。
昼頃にチームで集まって、会場に向かいます。会場の前にはコーチの堀先生が待ってくださっていて、お話ししたり写真を撮ってもらったりしました。会場に入ると、入り口で生徒証を見せたりするのですが、そのあたりのやり取りは全部英語で、わーアジア大会に来たんだという気分になります。ただ、今年は慶應がホスト校なので、スタッフの中にアルバイトで来ている同級生の知り合いとかがいたりして、割とリラックスできました。
クロークに荷物を預けて進むと、スナックエリアがあります。割と豪華に色々置いてあって、これを全部自由に取っていいとは太っ腹です。ペットボトルもあって、お茶やジュース、コーラなどもありました。朝コンビニで買ってきた手元のコーラを見て悲しくなりました。仕方がないのでチョコレートだけ頂いていきます。
指定された席に座って、荷物を広げたり、あたりをキョロキョロしてJAG合宿で会った方だー！ とか、牛の着ぐるみ被っている人がいるー！ とかしていると、そのうちに英語で諸々の説明が始まります。大事な諸注意とか色々。
その中でコンテストのシステムの説明が割と秀逸だったと思っていて、実際に前でスタッフの方が簡単な問題を解いて提出して見せたんですが、それがWAになって、Clerを投げて、testcaseをダウンロードして試してみたらコーナーケースで、直して提出してACという流れが、自然な流れで全部の機能を説明していてちょっと感動しました。
説明をそれなりに聞いて、それなりに聞き流していると、リハーサルのコンテストが始まります。 コンテストのシステムに慣れるためのものなので、気楽にやります。
問題内容は忘れましたがA,Bは割とやるだけだった気がしてすぐにAC。Cを見ると、前の木曜に学内の集まりでやった問題そのものだったので楽勝楽勝と思いました。チームメイト二人はそれに出ていなかったので、これは見かけはO(16!)で無理なんですが、実はそうではなくて、全探索でいけるんですよ、bitで集合を管理してDPをしてですね、と得意げに説明するんですが、解説を聞いただけで自分でちゃんと実装していなかったので、実はちゃんとわかっていなかった部分があったりして、バグが取れませんよ？ をやっていました。一度見た問題は、自分で実装できるところまでちゃんと理解しましょうね。
続いてチーム紹介が始まりました。競技に使っていたパソコンに各チームが用意してきたスライドが表示されるとともに、各チーム前に立って英語で色々とコメントしていきます。ネタに走ったスライドやチーム紹介が多く、終始楽しく見ていました。
僕たちのチームは、chokudaiさんが自己紹介時にハンドスプリングをするというのにあやかって、僕が側方宙返りをするというパフォーマンスをしました。僕らのチーム名はchoKOdaiなのでね。そこそこウケたのでよかったです。無理を言ってやらせてくれたチームメイトには感謝です。
ABC145
夜にAtCoderでABCがありました。レートが水色と青色の境目付近で青になれずに彷徨っていたので、今日こそ青に変色してICPC本番を迎えたいと意気込んで臨みましたが、ABCDの4完、レート-20で無事に冷えました。EもFもDPであることはわかっていたんですが、細かいところが詰められずに悲しかったです。ただ、DPだってのはわかったので実質全完だと言い聞かせて平静を保ちました。
ABC後に11:30くらいからcodeforcesのdiv2もあったのですが、さすがに次の日が朝早いので出ませんでした。
2日目 11/17(日)
無事に起床に成功したので、日本大通りに向かいます。電車でziroppeくんと合流し、駅でspiderさんとも合流。コンビニで適当にラムネとかを買って、会場に向かいます。あらゆる電子端末(腕時計含む)が持ち込み禁止なので、スマホとかを全部バックに詰め込んでクロークに預け、スナックエリアへ。コーラを手に入れます。今日はちゃんとコンビニで買わなかったのでね。
トイレへ行ったりライブラリの確認をしたりして時間を過ごしていると、前で説明があったりして、九時二十五分、コンテストが始まりました。
Aを見ます。パッと見てなんとなく3進数表現すると良さそう。二人にそのことを伝えて、入力を三進数表現に直すプログラムを適当に書きます。ziroppeくんはBを見にいきます。プログラムはできますが、単に三進数にしただけではダメ。考察していたspiderさんが、テープの速さを速くした後、戻す時に同じ速さをもう一回は繰り返さないといけないので、1桁目以外にビットが1以下の部分があってはいけないということに気づき、僕とspiderさんで書き上げます。ここまで40分くらい。提出してみると見事AC。
ziroppeくんにBの概要を聞きます。各定点が全ての各点にありうる値の範囲を与えるので、独立に処理して普通にいけそう。いけるねと言って、ziroppeくんと一緒にプログラムを書き始める。spiderさんには次に解くべき問題を探してもらう。ABは簡単だと明示されているけれど、それ以降はランダムな順なので。ただ、順位表を見るとHが解かれていて、それを重点的に見てもらう。
Bは各定点からDFSで波及させようとして、BFSじゃーん。いや、そんなことしなくてもマンハッタン距離じゃん……。という紆余曲折を経ながらもそれっぽいコードが出来上がる。ziroppeくんはきちんと隣り合う不定点同士が連続になるかが不安だったようで、僕も証明できませんでしたが、大丈夫大丈夫うまくいくよといって提出。ACしたので証明終了です。(あとからよく考えてみると、これあんまり良くないですね。ちゃんとある程度証明できる確信を持ってから出しましょう)
ここで順位表を確認してみると、40位くらいだった気がして、それなりにいい感じじゃないかなと思っていました。この勢いで3完しようと、spiderさんにHの様子を聞きます。どうやら構文解析みたいな問題のようです。
開き括弧と閉じ括弧でできた文字列がうまく整合が取れているかみたいなのを数え上げる問題で、これだけなら適当に残っている開き括弧の数とかを持っておけば前から順に処理できるんですが、面倒くさいのは'-'という文字があって、これがあると文字列が一文字消えるというので、これを処理するために、括弧での処理を適当なスタックに持たせてそれをpopさせながらロールバックするみたいなことを考えます。
なんとなくそれっぽいコードはできていきますが、spagetinizedされたなかなか見辛いコードを生成してしまいます。サンプルが合わないので三人でバグを洗い出していきます。だいぶ時間をかけますが、だんだんとわかってきて、サンプルケースも、適当に手元で作ったテストケースも全部通るようになります。いける！ とサブミット。WA。三人で頭を悩ましていると、ziroppeくんが、入力値ってint型じゃたりなくない？ と気づく。その通りで、long long に変えてサブミット。けどWA。
その後も色々と考えますが、結局WAが消えることはなく時間切れ。
三問考えていただけで、あっという間に5時間が過ぎていました。
終了後虚脱していると、色々と話があったりして、隣の会場へと誘導されました。そこでは、スポンサーの方のお話や、英語による問題解説などがありましたが、コンテストの疲れで完全に寝落ちしてしまっていました。
目が醒めると順位発表でした。ICPCの順位は、コンテスト中も順位表で確認できるのですが、終了30分前くらいに凍結して、更新されなくなります。その30分間で提出されたものの結果をYes/Noと言われる読み上げ形式で発表していって、最終順位が確定するというパフォーマンスがあるのですが、それで大いに盛り上がりました。一位のチームが、最後のところで誰も通していない問題を通していたりしてかっこよかったです。
それが終わると、元の会場に戻って写真撮影をして、懇親会が始まりました。企業賞の発表が前であったのですが、その間に企業ブースを回るという裏技を使って、Tシャツやステッカー、ファイルなど色々なノベルティを獲得していました。
乾杯をして立食パーティーが始まります。JAGで同室だった、こるとんさんやニクローさん、xxxkiritoxxxさん。今度行く予定のマニラ大会に同じく参加される東工大のチームmickythetaの方達。スタッフとして働いていた同級生。など色々な人たちと話せました。
あと、企業ブースでボンバーマンみたいなゲームをしたり、ボードゲームのガイスターをしたり、数独にチャレンジしようとしたり、なかなかに楽しみました。
最後の方で、Googleのブースに行って、入力と出力が与えられるので問題を推測しろという問題に取り組みました。この入出力のセットがいっぱいあって、人によって与えられるものが違うので、いっぱい会場を歩いて情報を交換しながら解こう！ という交流に向いたいい問題に思えました。入力は明らかに入力が有向グラフな上、会場の机に放置されている問題用紙にも有向グラフがことごとく書かれていたので、まあそういう感じの問題なんだろうなと、何人かで集まって解いていたのですが、全然わかりません。ウンウン悩んでいると、一人のすでに解いた方が現れて耳元で「それはひどい問題だよ」と呟きました。それを聞いて一人が何かに気づいたようで、その解法でみんなの入出力セットを確認すると、それでした。
Googleブースに行って答えを言うと、おめでとうと言われました。ひどい問題です。
後ろの方に強い方がいてその方もこの問題を解いていたのですが、全然わからないようで、すでに解けている人たちがオラクルをやってあげては、えー意味がわからない、と言うみたいなことをやっていて、上位のコーダーの人たちも人間なんだなと思いながら見ていました。
そんな感じでワイワイと交流を満喫しているとおひらきになりました。
皆に別れを告げて、ゆっくりと電車に揺られながら、次の日の中間テストの教科書を開きました。ICPCに集中していたので何一つ勉強していなかったので、１ページ目からスタートです……。
終わって
ICPC終わってしまいました。実はまだマニラ大会に行くつもりなのであれですが、予選通れるかどうかと言う感じで始まって、ここまで来れたのはよかったなと思います。
来年もこの場に来て、今度は今年以上の成績を残せたらいいなと漠然と思います。
まとまりのない文章ですが、そんな感じで楽しい二日間でした。
3日目 11/18(月)
ICPC三日目は、実は企業見学があります。でも平日月曜なのでね、授業はありますよ。中間テストもありましたよ。さすがに行けませんでした。ziroppeくんは月曜に授業があんまりないらしく企業見学参加したらしいです。水族館行きたかったな。
