ICPC2020参加記
ICPCお疲れさまでした。かなり遅れての投稿で内容もあまりありませんがゆっくり見ていただけると幸いです。
先にささっと結果だけ話してしまうと、僕らのチームは、黄水茶構成で3完でした。2時間半近く椅子を温めていて少し辛かったです。
学内に僕らより成績のいいチームがいたので予選落ちでした。
参加に至るまでの流れから本番までをだらだら書いていこうと思います。
唐突な参加登録
正直、今回のICPCは参加する気がありませんでした。登録とかめんどくさそうとか、同大で出れそうな人がいないとか卒論だりーとかそういうことを考えていたためもういいかなーと思っていました。
そんな矢先。
クロー大先生からお誘いをいただきました。(かなり嬉しかったです。)
もう一人が決まってなくて茶色(ねおさん)の方でもいいかーと聞かれましたが、僕としては参加できるだけで万々歳だったので僕がお茶くみ係になろうが靴磨き係になろうが寿司職人になろうがなんでもよかったです。
ただし、少し残念なことが僕としては元々ICPCに参加しない気で予定を組んでいたため、10月の土日の予定が埋まっていました。
チーム戦の雰囲気を掴むためにPGBATTLEとか国内模擬やるーっていう話をされたんですがまともに参加できませんでした、、、(そもそもPGBATTLEはチーム戦なのか諸説ありますが)
ただまあ、パイセンが国内模擬の日の体調崩したりしたのもあって後日みんなで問題解こうということになりました。
初めてのチーム戦
ICPCは少し特殊なのでチーム戦と言っていいのかわかりませんが……
とりあえずチームの構成が黄水茶でかなり凸凹構成だったのでどうしようかという感じになりました。(もはやチーム戦として成り立つのかこれ)
ねおさんには、ICPCというものの空気感を掴むために参加するそうなので、少し雑務よりなことをしていただきました。(提出の管理、出力の差分を取ったり……)
僕とパイセンは、僕が最近精進しまくってるのもあって僕は実質黄色コーダーということで二人で問題をいい感じに分け合って解くことにしました。
とりあえず模擬の問題を解き始めました。
ここらはチーム戦っぽく、Aは僕が解いてBはパイセンが解く。いい感じでした。
C問題から少し雲行きが怪しくなります。ぱっと見解法が思い浮かばない。なんだこれは。
ラバーダックデバッグの如くねおさんに俺の考えを聞いてもらいます。かなり考えがまとまって非常に助かった。
ただし決め手となる考察ができず、惜しいところをぐるぐる回ります。ここでパイセンがD解けねえと言いながら戻ってきました。
パイセンに改めてCの概要と考察を説明すると、パイセンもパッと思い浮かばないようでみんなでうーんとなりました。
ここで俺があるグリッドに侵入したところでカウントすればいいことに気づく。みんなで確かにとなる。
ただし実装がかなり地獄でした。とりあえず僕がある頂点からある頂点に侵入したときにカウントするみたいなコードを書いてパイセンがsxsygxgyの正規化をしましたが、無限バグ地獄に陥りかなり辛い気持ちになりました。
結局この日はCが通せず一旦解散となりました。
チーム戦リベンジ
次に集まったのはICPC前日のお昼でした。何しようかでとりあえず前回のupsolveをするかということになりました。
ちなみにC問題は正規化がバグっていたみたいでパイセンが通してくれて助かりました。
「バグ仕込み過ぎてこれじゃ俺バグ仕込ませのプロ・バグ駒瀬だよ……」って言ってたのが個人的にめちゃくちゃ面白かったです。
次にD問題、これもなかなか苦戦しました。各々で少し考えた挙句、詰まってしまったので少し話し合いをしようということで僕が最大最小をキープしたまま計算するのはどうか、という提案をしたらパイセンがめっちゃ綺麗にまとめてくれました。さすが黄色コーダー。
ということでこれを実装したのですがなかなか沼にハマってしまった。サンプルがあってるだけになかなか辛い。
こうなるとそもそも解法の正当性が大丈夫なのかという感じになるのですがあってそうなのでこのまま突っ切ることになりました。
最終的にごちゃごちゃやってたらなんかあってしまいACしました。(正直あんまり覚えてません……)
そしてE問題。C, Dがめちゃんこ難しかったからEも難しいんだろうなーと思ったのですが、見た瞬間にこれただの2-SATじゃん……となりました。
いやまさかそんなやるだけなわけないだろ、とパイセンと話し合ってたのですがどう見てもやるだけだったのでやるだけやってACしました。CDEでEが一番簡単でした。
そしてICPC本番へ……
当日。普段のコンテストの100倍緊張していて、前日の夜からかなり落ち着きがありませんでした。
というか僕は構文解析と幾何とサイコロを解いてなかったのでここらへんがめちゃくちゃ不安でした。
とりあえず昼に集まりリハーサルは参加して、軽く確認をしたら16時15分に集合、ということで各々散歩なりしてくることになりました。
僕はというと、手持ちにサイコロがなかったので買いに行くことにしました。
しかしロフトへ行っても置いてなく、近所の怪しげなおもちゃ屋に行っても置いてなく、ダイソーにも置いてなかったのでさすがに敵対チームの影を感じてしまいました。
しょうがなかったので紙でサイコロを作りました。
なかなか会心の出来でした。あわよくば解法ガチャもこのサイコロでやってやろうと思いました。
そして本番。めちゃくちゃ緊張しながら更新ボタンを押します。
……おそらく色んなところで言及されているので詳しくは省きますが、ICPC側のサーバーエラーで問題が表示されませんでした。
うちのチームのデータが登録されてないよ！みたいなことが書いてあったのでかなりひやひやしたのですが、10分ぐらいで表示され10分延長という文字もあったのでまあ大丈夫か、となりました。
模擬と同じく僕がA, パイセンがBを担当してささっと解く。そしてC, Dもそれぞれやる。
Cはかなりこどふぉっぽい問題だったのでささっと解けました。(実行終了前に提出してしまうトラブルがありましたが)
問題のD。全く解法が見えてきませんでした。
構文解析すらよくわからないのに、わかっていたとしても全く解法が見えません。
ここらで三人でとてもつらい気持ちになります。とりあえずEを見ます。
Eはまだわかりそうな問題でした。とりあえずパイセンが普通のDPを書いてみます。
答えが合わない……
普通のdpじゃダメなんだな、ってことはなんとなくわかったのですがどう重複を削除すればいいのかわからず……
そしてFを見ます。ここで僕は戦犯をしてしまいました。
初手でUnionFindが思いついたのですが、いつものコンテストのノリでO(N^2)の10^10だから無理だな～、いい感じにならし計算量で抑えられそうだな……という思考になっていました。
パイセンはパイセンでずっとEを考察していたので、お互いそれぞれの問題を考えこんで長く苦しい時間が流れました。
さすがにCを通してから2時間半あったのでDを考えなおしたりしたのですが、結局わからず……。
終了10分前に、Fの話をパイセンにしたら「ICPCなら10^10は許容範囲」と言われ、確かにそうなのかと思いました。
ですが10分で実装できるわけもなく、時間が来てしまいました。
最終的には3完学内2位で終わってしまいました。とても悔しかったです。
僕はB4で来年はもう就職するので最後のICPCでしたが、まあなんだかんだでチーム戦もこうやって悔しい思いをしたのも楽しかったです。
最後にここまで見ていただいてありがとうございました。これからもより精進していくのでよろしくお願いします。
(チーム戦お誘いいただければ喜んで参戦します！)
