裏紙

ほぼ競プロ、たまに日記

ACM-ICPC 2018 Asia Yokohama Regional Contest に参加しました

2018年12月8,9日に横浜でACM-ICPC 2018 Asia Yokohama Regional ContestにWAsedACというチームで参加しました。

メンバーはimulan(私)、ryoissy、yamadで結果は60チーム中10位でした。

早めに書こうとは思っていたのですが、結局遅くなってしまいました。簡潔に参加の感想を書きます。

1日目

お昼ごろからregistrationだったが、その前にコーチと4人で、registrationの前に中華街でご飯を食べた。この日はリハーサルとチーム紹介をした。

リハーサルでは__int128が使えるかとか、sampleをwgetで一気にダウンロードして遊んだりしてたら「正解が無いけど大丈夫ですか」的な感じでスタッフの方が来てすいませんってなった。

夜は近くのビジネスホテルに泊まった。ダブルの部屋に2人で泊まったんだけど、ダブルベッドに2人で寝るのはあまりおすすめできません。

2日目

この日はコンテストだった。コンテストの感想を細かく書く気力はないけど、自分の感想を簡単にまとめると

  • 傾向変わりつつあるかと思いきや、なんだかんだ実装量は多かった(めちゃくちゃ問題文長い、みたいなのがないので幸せ
  • 序盤悪すぎる(ペナルティが物語っている(+も多いし
  • PCの前に座ってから手が止まるシーンがあった(もうちょっと細かいところを詰めておくべき

疲れてて懇親会はあんまり交流できなかった...

3日目の企業見学も(完全に交流が目的になるが)余裕があれば行きたかったけど、行きたい気持ちを抑えて学校に行きました(できれば卒業したいので)。

おわりに

去年に続き、早稲田からは2チームがアジアに進みました。その6人のうち4人は今年で引退となりますが、来年以降もアジア予選に進むチームが複数出てほしいですね。ICPCがあることでなんだかんだモチベを保ってきた自分からしても、アジア予選に進めることは良い経験になりました。来年はそんなチームに多くの風船を配りに行けたらいいなと思います。

ACM-ICPC 2018 Asia Hanoi Regional Contest に参加しました

2018年11月29,30日に、ベトナム ハノイACM-ICPC 2018 Asia Hanoi Regional Contestが開催されたのでWAsedACというチームで参加しました。

メンバーはimulan(私)、ryoissy、yamad、コーチのtossyの4人で行きました。結果は125チーム中2位でした。

ベトナムの出来事、思い出を簡単に書き記そうと思います。

出発前

この3人でのICPCは最初で最後というのと、3人中2人がラストICPCというのもあり、1回ぐらい海外のAsia Regional参加したいねとなる。

選択肢は横浜と被っているヤンゴンを除いて、大会規模などを考慮してハノイジャカルタ、ソウルが候補になりましたが、韓国は魔境の匂いがしたので実質二択になりました。

ベトナムの問題セットを過去2年くらい見て、ハノイに行くことにしました。正直ジャカルタのセットはほとんど見なかったんですが、今年のジャカルタセットをチラ見した感じだとジャカルタでも良かったのかなあと思います。ただ、コンテスト全体の雰囲気は年による感じがあるみたいなので何とも言えません。

運営側がホテルを指定してくれて、「このホテルに泊まればホテルから会場まで送迎してあげるよ」って書いてあったのでそこに泊まることにした。ホテル代とか、参加費のために海外送金が必要になるのですが、色々と面倒が待ってるので早めにやるといいです(自分がやったわけではないが...大感謝)。ホテルには、ちゃんと送金したつもりが、足りなかったみたいで2回送金するはめになったりした。

出発前日にはホスト校のPTITの学生から"I’ll be volunteering for your team in the upcoming ICPC contest"ってメールが来た(大会中はほぼこの学生の方が案内してくれた)。もしものために電話番号とFacebook messengerを交換しておき、出発に備える。

11/28

移動日。朝7時に羽田に行く。空港でnarianZ(東工大チーム)に遭遇した。

ベトナムに(現地)15時くらいに着いて、ホテルまで行くためにタクシーで行くことにするが、タクシーのキャッチがめっちゃ強気で来たのでビビった。ICPCベトナムのサイトにタクシーの相場が書いてあったので、ちゃんといくらで行けるか聞いてからタクシーを選ぶことが出来た。

持ってきたガイドブックに乗ってたレストランで夕飯を食べるためにホテルから10分くらいあるいて夕飯を食べにいく。ハノイは信号が少なく、断続的に車とバイクが走ってくるので、間をぬうように道路を渡る必要があり、ヒヤヒヤしながら渡るけど、向こうも分かってるのでスピードを調節してくれる。ただクラクションは鳴らされる。

11/29

ラクティスの日。午前中にホテルに運営の方々が来て、Registrationとか、写真撮影とかを済ませる。Registrationとかをする前には、上で書いた私達のチームについてくれた方がコーヒー屋さんに連れてってくれた。めっちゃ甘くて美味しかった(絶対自分たちだけではこのお店に入る勇気はなかったと思う)。コーヒーを飲みながら、何を勉強してるのかとか、(1年生ということもあって)ICPCにあまり詳しくなさそうだったのでそういう話をした。あとはスマホの壁紙が"君の名は"だったので日本のアニメについても話した。ラピュタをおすすめしたら「見たこと無い」と言われたので「日本ではテレビで何回も放送されてる大人気作品です」と言っておいた。

午後からホスト校のPTITに移動し、開会式をした後にプラクティスがあった。

開会式の終わり際に、ジャッジからコンテストに関する説明があり、インタラクティブ問題に関する注意事項(flushしようね、みたいな)が説明され、それと同時に"""明日の本番では1問インタラクティブが出題される"""ことが明らかにされる。プラクティスに2問もインタラクティブがあったのでそれを考えたり実装したりした。システム自体はKattisを使っていたので、オンラインでKattisを使うのと変わりなかったので良かった。

ラクティスでは、Vietnam National Contest (日本でいうところの国内予選?)の問題のAからFが使われていた。

この日の夜は、海外チームは運営側が用意してくれたレストランで夕飯を食べた、日本勢(東工大、神戸大、筑波大)の方々と談笑しながら、美味しいご飯を食べた。

ホテルに帰ってから、L問題を考えて実装したりしてた。面白かった。

11/30

本番当日。コンテストは8時〜13時で、6時半にはホテルを出るというスケジュールだったが、意外と起きられた。

ここからコンテスト中の感想になるので、問題に言及する部分があるので、問題のネタバレを見たくない人は飛ばしてください。

順位表

チームの基本的な動きは、全員がパソコンに触る、2問以上を並行で進めていく(3人のリソースを1問に注ぎ込むというのは基本的に終盤までしない)、ぐらいです。

開始直後

開始直後からネットワークが重くて不穏。

始まったらA-D、E-H、I-Lに分けて問題を読み始める。自分はI-Lを読む。

yamadがAがいけるというのでとりあえず書き始めてもらう。

1通り書き切る頃には、もう自分はIJKLと読み終わり、CとHに正解が出てるので、Cを読む。Hはryoissyに考察を詰めてもらう。

Aが実はだめ方針だったらしく、Cはサンプルの説明をした画像が間違ってたから焦ったけどBFSをするだけなので自分がCを書く。

C AC(0:36)

そのままPCはryoissyに譲り、Hを書いてもらう。AはBFSベースで書いていたらしいが「よく考えたらパスが点素にならなかった」らしく、頂点に流量制約のあるフロー+その復元っぽいので考えてほしいと言われ、概要を聞いて、確かにできそうだと思うので自分が引き継ぐことにした。

H AC(0:56)

そのかわり、この辺りでI、J、Lに正解が出てるのでI、Jを2人に説明してから、自分がAのためにDinicを写経し始める。

自分がフローの復元で実装に手間取っている間に、Iの方針が固まったので書き始めてもらい、Jは「ループと完全グラフしかないんじゃないか」という結論になったので、それを出してみることにする。

J WA(1:47), I AC(1:51)

Jはきっと何か見落としてるんだ、と思い一旦おいておくことにする。この辺でLのclarがあり、問題文が修正された、というアナウンスがあったがネットが重くてclarが見れない。開始から2時間後くらいに、やっとネットが安定し始めてclarが確認できたので、Lをryoissyに説明し自分はAに戻る。

A WA(2:24)

結構自信があったので焦る。もう一度自分で問題をよく見直す。"shortest"って書いてあって、Dinicじゃできないじゃんってなる(見落としてたらしい)。でも、ちょっと考えると、グラフの形は変えずに、頂点に流量をつけた部分だけコスト1にした最小費用流の形にすれば、通過頂点数を最小にできることに気づき、最小費用流を写経する。

A AC(2:47)

この辺でJは頂点数が偶数だったら左右の頂点数が等しい完全二部グラフも条件を満たすということに気づいて、これで通らなかったらJは捨てるか、ぐらいの気持ちでJを出す。

J AC(3:04)

通ったのでテンションが上がる。そのままLをryoissyが書き始める。単語リストをソートし忘れたり、配列外参照をしたりしたが、程なくして通る。

L WA(3:16, 3:21), AC(3:22)

この時点で3位で、よりテンションが上がってくる。この時点で、残りの問題で正解者が出てるのがB、D、G(Gは1チームだけ)しかないのでそれらに絞ることにする。挑戦してるチームが多かったのはKで、幾何なので担当するなら自分になるが、順位表から方針を立てて実装したとしてもその後に絶対辛いデバッグが待ってると考え、Kは捨てる決意をする。

Dはインタラクティブなのでデバッグの辛さが思いやられたが、正解が多かったので、残ってる問題的にこれはやらないといけないと思い10分くらい3人でDを相談する。

けど、3人で1つに絞るのよくない、と思い、ryoissyだけはBのゲームを実験してもらうことにし、Dを自分がPCを使いながらyamadと一緒に考察することにする。

ずっと始点を固定して区間を伸ばしたり縮めたりすることを考えていたけど、どう頑張ってもクエリ回数が足りないので頭を抱える。

30分くらい紙で実験してくれてたBがわかったらしいので、実装してもらう。

B AC(4:09)

この辺から(テンションで)自分たちがうるさくなってきた(と思う)。

Dは、長さを固定して始点を動かすようなクエリを投げると、毎回答えの位置の候補を半分に絞れそうな気持ちになり、それを実装する。この時書いた二分探索が、閉区間による実装になっていたため、クエリが足りなくなったり細かいバグを踏んだ。

D WA(4:23, 4:28), AC(4:38)

残りの時間はGを考え、辺が多い方はできそうだけどねー、みたいな話をしながら祈っていた。

↑これだけだとネットワーク悪くてちょっとイライラしただけ、みたいに見えますが、実際は前半2時間の時点で3完だったのでそのせいもあって内心はイライラと焦りがやばかったです。

焦りはしましたが、結果的には、自分がCAD、ryoissyがHLB、yamadがIJみたいな感じで実装を担当し、PCが空いてしまう時間がほぼなかったので良かったです。

順位表から、8完の可能性があるのは4チームで、うち1チームにはペナルティで勝てる見込みがあったので3位以上になりそうなことがわかり、もう気が気ではなかった。

閉会式は夕方で、その前にエクスカーションがあり、ハノイ郊外にある陶器の工房みたいなところとマーケットを見学して回った。バス移動で片道1時間かかったが、チームメイトとか、PTITの学生(2,3人)としゃべってたら移動はあっという間だった。自分たちと話してたPTITの人は日本に興味があるって人が多くて、日本語も少し喋れる人もいた(すごすぎる)

大学に戻ってきて、閉会式、YesNoが始まる。

YesNoの動画は自分でも撮ってたけど震えてて使い物にならなかったのでTumoiYorozuさんのツイートを引用させていただきました(ありがとうございます)(再生回数の15回分くらいは自分です)。

壇上で表彰状、金メダル、トロフィーを頂きました。

そのまま大学内の屋外会場でディナータイム。NCTUのコーチっぽい人に、「NCTUは台湾で2位だったから僕たちがWF行ける確率上げるために君たちが横浜でも2位以上獲ってくれ〜〜」みたいなことを言われて、がんばります...ってなった。

ホテルに帰ってきてPTITの学生の人たちにも挨拶をする。次何したらいいかよくわかんない時もすぐに案内してくれたし、本当に良い方々だった。

12/1

移動日。出発は15時くらいだったので、午前中は余裕があったら観光するか迷ったけど、起きたら雨めっちゃ降ってたし、気力もなかったので、ホテルの目の前のショッピングセンターを30分くらい見て回るぐらいに留まった。

22時に羽田に着く。ハノイは25度くらいあったのでとても寒い。

おわりに

以上の3泊4日で、ベトナムに行ってきました。ご飯おいしかったし、現地の人優しかったし、何より成績が良かったので思い出に残るICPC海外Regionalでした。横浜でもがんばります