TechFULの中の人

triple-four’s blog

ICPCアジア地区横浜大会2018体験記

こんにちは!
必修科目の締切が頭が悪いほど短く、 僕たちを留年させに来ているとしか思えないガナリヤです。

突発ながら、今回、ガナリヤは、siiiec・C_avaとともにICPCアジア地区横浜2018に参加してきました。 今年ICPCに僕たちは初参加だったのですが、運良くインターネット予選を通過し、アジア地区大会に出場することができ、12/8, 9に横浜に行ってきました。

今回はその体験記をまとめてみようと思います!


初日(リハーサル)

朝5時に起床ACしました。つよい。
朝早いからか非常に寒く、オフトゥンに入りたい気持ちと30分ほど葛藤してました。
その後、二度寝TLEをなんとか避け、新幹線で横浜に向かいました。
新幹線内ではすることがなかったので、論文を読んだり、数学の勉強してました。(真面目か)
前の席ではC_avaは気持ちよさそうな顔を浮かべ、siiiecはスマブラをこすっていました。
誰一人アルゴリズムなどの復習をしておらず、あば^〜と思いながら無事東京に着きました。

東京の人の多さにビビりながら、電車で横浜に移動し、なんとか会場にたどり着くことが出来ました!

f:id:ganariya:20181216145308j:plain
ICPC会場

ICPC初日は、リハーサルと自己紹介で、二日目が本戦でした。
会場に入ると、なにやら自分たちに似た人たちがいっぱいいました(エンジニアがみんな似ているのとアニメアイコンなのは余の常)。
ここらへんから自分の緊張はピークに達し、用意されたパソコンの前で、はやくもチームのマスコットと化してました。

🐜本や、筆記用具の用意をしたり、チームメンバーと談笑していたら、あっという間に時間が経っていたらしく、主催者の方々のお話が始まりました。
ICPCアジア大会では、海外からのチームもいるため、発表や問題、スタッフとの会話は全て英語でした。英語さっぱりわからないと思いながら、主催者の英語に分かっている素振りをするのを頑張っていたのが記憶に残っています。

その後、リハーサルがついに始まりました。
リハーサルでは四問出題され、基本的に過去のアジア地区の問題が出ていたようです。
B問題は先日チーム練習で解いたばかりであり、siiiecがスラスラ通してました。
C問題は、巡回セールスマンの応用っぽい問題でしたが、リハーサルの時間切れを迎えました。
今思えば、あのときA, B問題をさらっと通すのではなく、WAやTLEなどをしてマシンパワーを確かめたり、どれぐらい定数倍の遅さが出るかをチェックするべきだったと思います・・・反省ですね。

リハーサル後に、チームの自己紹介を自分が英語でしましたが、英語の出来はガバガバでした。自分は日本人なんだなと改めて思いました。来年はもっと面白い自己紹介にしてやる。

その後問題の反省をしながらホテルに移動し、夜ご飯を三人で食べに行きました。
せっかく横浜までにきて、チェーン店は嫌だったので、地元の中華屋さんに入りました。麻婆豆腐定食を食べましたが無茶苦茶おいしかったです。あと量が尋常じゃなく多かった。来年もまた来たいです(はたして来年は来れるのでしょうか・・・)。

f:id:ganariya:20181216150423j:plain
夜ご飯

夜中はスマブラをしてました。(アルゴリズムの復習をしろ〜〜)
大学で所属しているサークルは運動部ではなくインドア系なので、こういう泊まり込みは大学生になってから殆どなかったので、修学旅行気分ですごい楽しかったです。
来年もまたこのホテルに来たいです(だから来年は来れるのry)。
あとC_avaが半袖短パンのワンパク小僧スタイルで寝てて面白かったです。

僕は緊張して全然寝れませんでした💢💢💢(自分に打ち勝っていけ〜)


二日目(本戦)

会場から少し遠いところにホテルがあるのと、本戦自体の開始時間が早いので、六時起きでした。アーメン。
眠い目を擦りながら、ホテルの朝食を食べ、横浜の電車にキレながら再び同じ会場につきました。
昨日と全く同じ会場でしたが、やはり本戦の緊張感からか昨日より会場がピリピリしていて余計緊張しました。

会場で問題を解く順番やコーディングの話などの作戦立てをしていたら、いつの間にか開始時間であり、心の準備が出来てないままさらっとコンテストが始まりました。
今思うと、切り替えがきちんと自分の中で出来ず、頭が稼働しているフリを一見見せながら、実のところうまく動いてなかったので、あれはまずかったなと思いました。

コンテストが始まると、他の二人にA問題を任せ、自分はコーディングの事前準備をしていました。

ICPCのコーディング環境はUbuntuであり、今回使用した構成は

でした。
僕は普段からMacでCLionを使っており、他の二人はWindowsVisual StudioVisual Studio Codeを使っていました。
ICPCの環境にはVisual Studio Codeが入ってなかったので、CLionが今回は選択され(Vimとかemacsもありましたが僕たちは誰も使わない)、僕がインクルードやファイル構成の準備をしていました。
来年はVisual Studio Codeも入ってほしいものです・・・

テンプレートやファイル構成の準備が終わると、siiiecが解法が生えたようなので、siiiecとC_avaがA問題を解き始めました。
僕もA問題をちらっと読みましたが、問題内容自体がよく頭に入ってこなかったので、B問題を読んでました。

B問題を考察していると、siiiecとC_avaのコーディングが終わったらしく、A問題を提出したところWAが生えてました。
どうやら文字列から数値型に変換する時に、逆側から(123なら321)と変換していたらしく、ここのやり方は自分が構文解析で知っていたので、そこを自分が修正して、何度かテストして提出したらACが生えました。
自分だけだとおそらく今回のA問題は解けませんでしたが、siiiecとC_avaがAを解き、自分が少し直して通ったので、こういうのがチームで解く楽しみだなって思いました。
ちなみに、僕が今回活躍したのはここの数字の変換だけで、あとはチームの無能マスコットやってましたごめんなさい

その後三人でB問題を考察しました。
与えられた数列の最長の長さの等差数列の長さを出力せよという問題でした。
この問題にだいぶ時間を取られ、紙に書きなぐりながらうんぬん言ってました。

しばらくしてから、自分がグラフに変換して差を辺として捉えてスケジューリング問題っぽくマージしながら解くという解法が生え、実装しましたがTLEでした。
mapを使ってこの時は実装しており、mapより早いがソートされていないunordered_mapを使い、findで枝切りしながらやると間に合ったらしいので、データ構造をきちんとブラックボックスとしてではなく、内部実装も理解したほうが良いんだなと思いました。
なお、自分やsiiiecの考えた解法はN^{2}logNでしたが、公式の想定解法はN^{2}だったようです。ああ人生。

その後、siiiecが解法が生えたらしく、二分探索解法であり、実行時間が6sで、制約の5sより1sだけ長いなってなりました。
ここで、ガナリヤのミスが響いたわけですが、ガナリヤの作ったランダムテストケースの入力数が、問題の制約よりもかなり大きくなっていたらしく、正しい入力サイズのランダムテストケースにしたらギリギリ間に合いました。
チームメイトをも騙す、チームのマスコットガナリヤ。これは害獣ですね間違いない。

Bも通り、その後C問題を三人で読み始めました。
ここで、またガナリヤはやらかしたのですが、問題文を正しく読み取れておらず、コンテスト後の解説の時間まで問題を勘違いしていました。
そんなわけで、二人の解法と話が合うわけがなく(問題がもっと複雑と勘違いしていた)、再びマスコットになりました。
二人は解法が生えたらしく、実装を始め、僕はマスコットらしくG問題を読んでました。
あ〜これG問題セグメント木とかで殴るやつだ時間があれば解けそうと思いながら時間が残り少なかったので(また人生)、二人のコーディングを見ながらC問題のチェック用テストケースを作ってました。

しかし非情にも、本戦の時間終了となり、僕たちは二完で初めてのICPCを終えました。

終わってから自分の周りを見渡すと、他のチームには、いっぱい風船がついているところがあり、五時間でこんなにも違うのかとただただ驚かされ、もっと強くなりたい、コーディングがうまくなりたいと切に思いました。
自分の力不足を再確認した、そんな一瞬だったと思います。

本戦が終わってからは横須賀市民ホールに移動し、審判団による講評がありました。
コンテストでだいぶ頭が疲れていたからか、または英語がよくわからなかったのか、眠気がひどく途中スヤスヤしながら聞いてました。
H問題当たりの解法やべえなって思った記憶があります(こんなの思いつかんやろってなった)。

そして、審判団による講評が終わると、ついに最大のイベント「順位発表」が始まりました。
ICPCでは、基本的にコンテスト中、全てのチームの順位表や正答率が見ることができ、いっぱい解かれている問題があったりするとその問題を解きにいったりするのですが、終了三十分前になると順位表が凍結され、全てのチームの終了三十分の提出か非公開情報となります。
その非公開情報を最後に「Yes/Noおじさん」と呼ばれる人が、終了三十分の提出が正しいのかを読み上げていきます。 以下がその動画(1時間24分頃から)です。


ACM-ICPC 2018 Asia Yokohama Regional Contest - Commentaries on Problems, Award and Closing Ceremony

Yes/Noおじさんの読み上げ方も美味いのも相まって、最後の30分にどのチームが提出を成功させたのかドキドキしながら食い入るように見てました。
特に最後の一位と二位では、先に二位のチームが最後の12問目を通し、さらに最後の中国のチームも12問目をギリギリで通しており、なにか感動的なドラマを見ているような気分になりました。

楽しかったYes/Noおじさんイベントが終わり、その後元いたコンテスト会場に移動して、お疲れ様パーティーが開かれました。
立食パーティーをしながら、企業賞を授与したり、企業の説明会をするというものでした。

株式会社ドワンゴのブースでは、ハイパーロボットというボードゲームをやってました。
ボード上のロボットを移動させて、ゴールまでの最短移動回数を求めるという、如何にも競プロっぽいボードゲームでした。
このボドゲで勝つことはできませんでしたが、ニコニコ動画のマスコットキャラ、ドワンゴちゃんマスコットが貰えました。なぜか親近感湧いちゃう。

その後、色々な企業のブースを見ましたが、もう僕は精神的にも体力的にも疲労していたため、あまり覚えてないのが実情です。体力つけたい。

その後電車でホテルに帰り、会場でもらった企業のグッズや食べ物の整理をしました。なんか変なテンションでやってました。

f:id:ganariya:20181217204903j:plain
ICPC

siiiecが一人でエナドリ三本くらいもらっててやべえやつだと思いました。C_avaはまた半袖短パンだったのでやべえやつだと思いました。

そんなこんなで僕たちの長かったICPCは幕を閉じました。


最後に

ICPCは、今年僕が、C_avaとsiiiecにと参加しないかと何気なく誘ったのが始まりであり、まさか今年アジア地区に行けるとは思ってもいませんでした。
思い描いていた構図としては、

  • 今年のICPCはインターネット予選落ち
  • くやしい
  • 来年がんばるぞ
  • 来年通る

みたいなものでした。
その分来年はもっといい成績を出す必要があります。

ICPCアジア地区予選に参加してみた結果、思ってたよりずっと楽しく、色々な人と交流できたり、色々な経験を積むことが出来ました。
しかし、楽しかった反面、他の大学の強い人達の頭の良さやコーディング力を目の当たりにし、自分の圧倒的力不足を感じました。まだまだ自分には精進が足りていないようです。

大学三年間で、ICPCアジア地区大会の三日間は一番楽しい出来事だったと思います。
また来年参加してもっといい成績を出すために、今年一年毎日精進していこうと思います。

ガナリヤでした!