【No.026】「ACM-ICPC2016アジア地区つくば大会の参加記」
順位表 ( 凍結解除済み )
http://icpc.logic.cs.tsukuba.ac.jp/standings/
僕たち 575.cpp 結果は8完で4位でした。(大学順とチーム順の両方とも)
0日目 10月14日(金) コンテスト2日前
朝8時に起床。午前中は3時間ぐらい友達の家でゲームをやりました。
午後はライブラリの確認をしたあとに、AOJで1問解きました。
Modern Announce Network | Aizu Online Judge
AIZU ONLINE JUDGE: Code Review
およそ1年前の模擬地区予選に解法を考えただけの問題だったのですが、完全に記憶から抜け落ちていました。途中で一気に当時の記憶が蘇ってきたような感覚になってすっきりしました。
( そのときの模擬地区予選の記事→dohatsutsu.hatenablog.com )
1日目 10月15日(土) コンテスト前日
朝6時に起きてから準備をして大学に向かってライブラリの追加印刷を行いました。
そのときチームメイトの後輩と出会ったのですがその後輩の髪が・・・
会場に到着すると、黄色いTシャツを着た会津大学OBの方々と再会して懐かしい気持ちになりました。
(OBの方々と話しているときにYazaten君と遭遇したので、忘れないうちに会津合宿のときに置き忘れていってしまった充電器を返しました)
懇親会ではいろいろな人と交流しました。(大阪大学の人とか埼玉大学の人とか)
チーム紹介のスライド発表もなんとか無事にやり過ごし、後輩の車でホテルへ戻りました。( このとき道に迷って大変だった )
自分のiPhoneのマップに従い、さて君の車でホテルに移動。
— kzyKT (@kzyKT_M) 2016年10月15日
マップに騙され何もないところに連れて行かれたので、ARCに間に合わなかった。
ホテルに到着した時点で9時を少し過ぎており、ARCはあきらめて、すぐに眠ることにしました。
2日目 10月16日(日) コンテスト当日
朝6時に起きてシャワーを浴びて朝食を食べてコンテスト会場まで移動して・・・
とても朝は忙しかったです。
8時45分、いよいよコンテストが開始。
コンテスト開始と同時に封筒を破ったら封筒の中にある紙も破いてしまって自分でも笑ってしまった。
まずは自分がマシンにログインして環境設定を行いました。
まず、 CapsLockキーをCtrlキーに変えてくれるコマンドをターミナルで打ちます。
次に、僕たちのチームは全員がemacsを使ってコードを書くので、 init.el というファイルを作って flymake の設定を書き込みます。 ( flymake はプログラムの文法を自動チェックしてくれます )
最後、.bashsrc ファイルに
alias g++='g++ -O2 -std=gnu++11'と書くはずが
alias g++='-O2 -std=gnu++11'と書いてしまい1分ぐらいロスしました。
(kzyKT先輩に指摘されて気づきました。)
環境設定が終わった時点で8分ぐらい経過していました。
環境設定が終わったら、手筈通りすぐにkzyKT先輩に交代し、A問題を実装してもらいました。また、交代するとき、C問題のとてもざっくりした概要を聞きました。
C問題は図があるおかげですぐに概要が把握できました。
ある地点に到着するために選べばよいスタート地点のIDの集合は{1,2,3}とか{3,4,5,6}というふうに連続した整数の集合になっていて、{1,3} とか {2,3,6} というように整数が飛んでいることは無い、ということに2分ぐらいで気づいて、それに気づいたら一気に考察が進みました。
後輩がまだB問題の読解に詰まっていたので、先輩がAを解いた後は僕がC問題を書きました。
C問題が解き終わったあとはB問題を担当している後輩に交代しました。
そして先輩からD問題の概要を聞いて、4000C2個の部分文字列のハッシュを列挙できれば解けることが分かり、僕が実装することになりました。
後輩がB問題の実装で詰まったので、交代してもらい、D問題の実装をして提出するもTLEになってしまいました。すぐにD問題を印刷して後輩に交代しました。そして後輩がB問題を書いている間にコードを見直しました。
高速化の方法がハッシュを map に詰めるのではなく、unordered_mapに詰めるようにするしか思いかず、後輩がBを書いている途中に1分だけマシンを交代してもらい、mapをunorderedmapに変えて提出したらACしました。
その後すぐに後輩がBを通してくれて、その時点ではなんと1位になりました。
後輩にF問題を読んでもらい、自分は先輩からE問題の概要を教えてもらうことに。
どうやらE問題は
Lost Number | Aizu Online Judge
とほとんど同じ問題だったので、この問題を解いたことがある僕が実装することになりました。( AOJ-ICPC 埋めをしていて本当に良かったと思いました。 )
E問題を実装している途中で後輩がF問題の解法を思いついたようなので、実装に詰まるたびにマシンを交代しながら実装していきました。
E問題は1回WAを出してしまいました。バグの内容はすぐに見つけることができて、
3文字書き換えるだけでした。
(致命的なバグであることにもかかわらず偶然にもサンプルが一致してしまったようです。)
Eを解いた後、後輩がFのTLEで苦しんでいたので少し相談することに。
コードを読んで高速化のアイディアを出して再び実装してもらい、その間に先輩からG問題の概要を聞きました。
考察をしていくと、「○○ができれば解ける」という閃きから、「○○をやるためには、□□ができなければならない。」→「□□をやるためには、△△ができればよい」というふうに徐々に前に進んでいって最終的な解法にたどり着くことができて面白かったです。
(とはいえ、もっといい方法がある可能性が高いです・・・)
F問題を担当している後輩とときどきマシンを交代しながらG問題を実装していきました。
コンテスト開始から2時間19分経過した時点でG問題がACしました。
G問題がACした後はF問題を完全に後輩に任せたまま、先輩と一緒にI問題の考察をしたり、J問題を読んだりしました。
J問題は、円と凸多角形の共通面積を求めるライブラリを持っていたので、「これは解くしかない」となりました。
会津大学OBのzukkyさんとNCAstarさんが作ってくださった円と凸多角形の共通面積を求めるライブラリを頑張って書き写して、それを印刷して先輩に書き写しのミスがないかチェックしてもらって、2重の、 3分探索を書いてACしました。
書き写しのミスが2,3箇所あったので、見つけてくれたkzyKT先輩には本当に感謝しています。
zukkyさんとNCAstarさんにも感謝です。
俺が後輩チームに残したライブラリの中で、NCA君が作った問題のテストのために必死こいて作った円と多角形の共通面積を求めるライブラリが本番で大活躍したみたいで、最高に熱い展開だ
— zukky (@zukky162) 2016年10月16日
J問題がACした時点ですでに残り時間は74分でした。
順位表を見るとF問題とI問題が解かれていて、僕は後輩のサポートをすることにしました。
後輩が実装している方針をもう一度聞いて、コードを読み直すと、すぐに駄目なケースが思いつきました。解法の基本的な方針はあっていそうだったので、解法の詰めの部分を一から考察しなおすことにしました。
なんとか時間内に正しい解法にたどり着き、後輩に実装してもらって1回WAを出しながらもACしました。F問題を解き終えた時点ですでに順位表は凍結されており、残り時間は18分になっていました。
残り時間では、I問題に先輩や僕が直感で考えた解法で挑戦したもののダメでした。
表彰式では1,2,3,5位のチームが壇上に立って商品を貰っていて、悲しかったです。
コンテスト終了後、懇親会へ。
懇親会では企業ブースで出題されたクイズを解くことに夢中で、あまり食べることができませんでした。
表彰式で景品をもらえなかったチームの中で最も上位だったためKlab社からモバイルバッテリーをもらうことができました。とてもうれしかったです。
チームの名前がアナウンスされても後輩がなかなか姿を壇上に表さず、何枚かは後輩がいないまま写真を撮ったりしました。
あと、その場の勢いでそのとき近くにいた会津大学OBの方とも一緒に写真を撮りました。
懇親会のあと、いったんホテルの部屋に戻って荷物を置いたあと、
一部のコンテスト参加者たちとの2次会に参加しました。
(ホテルの部屋に戻ったとき、筆箱を置き忘れてしまったことが発覚して、ちょっと大変でした。)
こういうときにしかできないい話をいろいろ聞いたりできて楽しかったです。
2次会が終わってホテルの部屋に戻るとき、 kyuridenamidaさんに突然「頭がいい」と言われました。
3日目 10月17日(月) コンテスト翌日
後輩が2次会のあとカラオケに行ったらしく、寝不足でしたが無事に会津に到着できました。会津に着いてからはニコニコのタイムシフトでつくば大会の生放送を見ました。
おまけ ニコニコのタイムシフトの感想
結構会津大学の話が出ていて驚きました。
生放送で僕らのチームのページが表示されたときのことを考えて、順位表の自己紹介欄にAtCoderのIDを載せていたので、良かったです。
( chokudai さんが、topcoderのidはあるのにatcoderのidがないことを嘆く→僕がidを書いていることに気づく という流れがまさか本当に実現するとは思わなかった。)
怒髪という名前から、青い髪の毛の人だと勘違いされそうになったり、コメントで何度も青髪DQNのチームとよばれていたりして悲しかった。