ICPC2020アジア地区予選 参加記
今年はオンラインでの参加です。
早稲田からは1チームのみの参加となってしまい、プレッシャーを少なからず感じていました。
国内予選参加記↓
1日目
学生証確認と練習のコンテストが行われました。
チーム名が呼ばれている様子や、judgeの使い方の説明で怪しいACが出たりしてゲラゲラ笑っていました。
WAを出したら積極的にclarに投げていきましょう（いいえ）
練習コンは無事全完でき、ジャッジの確認もできたので一安心。
翌日の起床が怖くなってコーチに電話番号公開が行われました。
その後はAOJ-ICPC等を埋めたり、サークル仲間でAmong Usをしていたら2時半くらいになったので祈りながら就寝
2日目
7時半起床 起床界のtouristですって言いながらTL眺めたら無限人起床していてびっくりしました。
3人とも無事起きれたので良かった…！
コンテスト
いつも通りA : siro、B : suta、C以降kiyoshiで始めました。Aを読んだsiroが早々にkiyoshiに概要を伝えて問題をパス。kiyoshiがすぐに解法を思いついたようで難なくAC(0:16)。判断が早い。
Bを読み終わると小さい順に入れていくだけなような気がします。程なくして書き終わって出すとWAが出てしまいました。
するとすぐにsiroがhackケースを与えてくれて、悶えながら実装を修正しました。AC(0:46)
チームThe atamaが爆速でJを通しているところに目をつけたkiyoshiがJを読み終えており、概要が伝えられました。BFS/DFSでよしなにできそうだな～→できましたということで書きます。AC(1:10)
C～Kの大海原の中でThe atamaに救われたのは我々だけではないはず（？）
Gの読解に加わり、読めたところでsiroがIの読解、kiyoshiとsutaでGの考察を進めました。二分探索はできそうにないので昇順に見ていくしかないということになり、これはUnion FindとUndo可能Union Findで管理すればよいです。その時に題意を満たす条件がO(1)で判定できるが問題になりますが、kiyoshiが必要条件を見つけ、大丈夫そう(お気持ち証明)ということになり、kiyoshiに実装を任せてIの考察に加わりました。
おそらくこの動きがまずくてGの実装は自分が担当すべきでした…
Iは箱根DPっぽいという気持ちになってsiroと考察を進めますが、数字が既に1箇所だけ出ている箇所の処理が思い浮かばず1時間ほど冷やしていました。その間にGの実装をしているkiyoshiが唸っていて、大変そう…(小並)という気持ちでIと格闘していました。オフラインなのでUndo可能UnionFindすらいらないらしく、自分が実装すべきだったと後悔し始めました。
siroがIから撤退してパズルっぽいCに行きました。しばらくすると
「これ少ない手数でいけたりしないかな」
という話になり、確かにsample output 4が賢くて、右手法とかで確実に5,6手で行けるならありえそうという気持ちになりました。5手でもgoto 1～5、if open 1～5、forward、left、rightを全探索しても135×NMくらいで間に合いそうなのでとりあえず全探索を書いてみようということでsiroが書き始めました。
kiyoshiはGでメンタルが崩壊していて、sutaもIで方針が立たず苦しんでいて、気づけば残り1時間半くらいになっていました。
Gとの戦いで辛くなっていたkiyoshiが、かすれた声で
「もうこれ落ちたらしらないよ～～～～～」
と言いながら提出するとAC(3:53)。本当にお疲れ様でございました……
ここまでずっと3完のままだったので、UHISHIRO大丈夫か…？と心配になっている方も居たかもしれません
siroがCの全探索コードを書いているので、Gを終えたkiyoshiがCのヘルプに回ります。このあたりで突然Iの考察が生えます（！）
もう一度冷静にsample input 1で考えてみました。
'I'のindexと'O'のindexを上下に並べ、2回出てきている数字はカットして、数字が1回のみ出てきている数字のindexに色をつけてみます。
1 2 4
3 5 7
左から順に、'I'1つと'O'1つを同時にペアリングして同じ数字を割り当てることを考えると、各'O'のindexに対してペアリングできる'I'の場所の種類数は単調に増加していきます。すると自由に数字を割り当てられるindex（上でいう黒い数字）にi番目まででj個割り当てたという状態を持つことでDPによる遷移ができそうです。
sampleで手計算DP(謎用語)をすると答えやDPテーブルの結果が合うのでこれだ！となり実装を開始しました。
Cで二人とも頑張っていそうなのと、もう凍結段階に入っていて時間がなかったので解法の伝達は行わず、こっそり実装をします。
遷移も考察段階で詰められていたのですぐに書き終わり、提出するがWA。申し訳ないと思いながら焦っても無駄なので冷静にコードを見返すと一部カウントを怠っていた箇所があることに気付きました。修正してAC(4:19)。肩の荷がおりました。
Cは2人でバグ修正を繰り返していたので、EとHを読みにいきました。Eは概要を把握すると、最小包含円っぽいけどヤバそう…という気持ちになり、Hを読み始めます。
ここでついにCの実装が終わり、サンプルが合いました。提出するとWAが返ってきます。なんで……？？？と言っていたら凡ミスをしていたようで修正して出すとAC(4:41)。
その後Eの概要を伝えると無理そう～となったのでHを考察するも、K=1ですら撃沈。ジャッジに"MURIDESU"(文字列)を投げてコンテストが終了しました。
結果
6完21位でした。よく頑張ったと思う反面、あと1問くらい取りたかったという気持ちもあり、少し複雑です。終盤の3並列がしっかり決まったのがせめてもの救いでした。Yes!を世界に届けられたのが嬉しかったですね。
弊チームは中盤冷えがちなので、直していきたいと思っています。
21位ということで企業賞を頂きました。メルカリさんありがとうございます。
コンテスト後
専用ツール「gather」で懇親会が行われました。前半はjupiroさん、Lorentさんとお会いして話しながらYouTube Liveを見ていました。チームonionsのコンテストの様子や問題の解法の話だったりLorentさんの神記事
区間に辺を張るテクの実装例（Dijkstra法セット）と使用例 - Lorent’s diary
の話をしていました。
Yes/Noで腹筋がもっていかれました。初っ端から面白いのは、ずるいだろ
その後NOSSさんと久しぶりに話しました。NOSSさんと話すたびに思い出深いACPC2019がよみがえってきます。
当時のオンサイトでは天上界だった方々と今張り合えているということにとてもエモくなったりしていました。
NOSSさんもまた来年があるということで対戦よろしくお願いします。
cirnoさんnasatameさんふるやんさんともお話させていただきました。オンサイト時代の横浜大会の話を聞いてあああああああとなったり(語彙力…)、再び記事の話もしていました。ふるやんさんの神記事
競プロのための高速フーリエ変換
cirnoさんがヤバ問の話をkiyoshiとしているのを聞いてやべーと言いながらお菓子を食べていました(は？)
終了時刻も近づいてきて俳諧を始め、チームtsutajのTABさんとmonkukuiさんとお会いしました。国内でも地区予選でもチームtsutajとは1位差で密かにライバル意識がありました。やっぱり「tsutaj」の文字列を見ると一瞬反応してしまいます。連続する部分文字列に「suta」があるので。
まだgatherに30人ほど居るはずなのに人が見当たりません、cirnoさんが「follow」機能(特定のユーザーのところに自動で言ってくれる機能、これマジで便利、オンサイトでもほしい(え？))で探したところ、ド辺鄙なところに10人ほど固まっていて面白かった…
ピクトセンスで小学生並の下ネタでゲラゲラ笑っていました。早朝から叩き起こされていたので実質深夜ですね、うん。
gatherはここで解散となりましたが、その後も三次会（？）でボドゲやAmong Usをしていました。めちゃくちゃ楽しかったです。
最後に
いろいろな人と話ができて楽しかったです。チーム練以外でこんなにしゃべるのはいつぶりかな…
オンラインと聞いたときはとても悲しくなってAOJ-ICPCに手がつかなくなっていたのですが、徐々にモチベーションも回復して本番では楽しむことができたので良かったのかなと思います。
運営の方々はもっと大変だったと思います。本当にありがとうございました。
オンサイト渇望してるので次回は是非オンサイトでお願いします！！！横浜行きて～～～～
次回間違っても予選落ちしないように精進していきたいと思います。kiyoshiが来年で卒業ということでUHISHIROフルメンバーでの参加は次回が最後です。頑張ります。
