ICPC2021国内予選 参加記
解法への言及があります、ご注意ください
suzuken君、bayashiko君と「MSB」で出ました。AtCoderにおけるIDの頭文字をとってきたものです。
前日になって何故かスポンサーが突如ついたらしいです。
今気づいたんですがなんですかこれは？？？ pic.twitter.com/3OFw3XqL9W
— おふとんらぼ@プロコン用 (@MohutonLab_comp) 2021年11月4日
コンテスト前
コンテスト前日はPCを22時くらいにカバンにしまっていたので、手持ち無沙汰になりました。高校からの親友に電話して、一緒にスマブラをしていました。彼は最近競プロを始めたので、ICPCについて語りながらプレイしていると、スマブラでボコボコにされていました。
コンテスト当日、開始は16:30なのですが、お昼は外で食べようと思い、12時に着きました。が、全くお腹がすかないので、散歩をすることにしました。
理工キャンパスから本キャンパスへ行き、ふらふら歩いていました。
明日は早稲田祭があるらしく、いろんな学生が忙しそうに移動していました。僕には縁のない話です。
そんなこんなで1時間ほど歩き続けました。
帰り道、ドン・キホーテに寄り道をすると、アルフォートが70円弱で売っていました。ここに毒を盛れば、弊学の5チームを全て闇討ちできる！そう思い、ニコニコして購入しました。
14:00あたりから、ぽつぽつと人が集まり始めます。自分は、一旦同期の人達と雑談をしていました。その後、コーチをしてくださっているとまとさん、るぎうさんがいらっしゃって対応していると、同期に「敬語使えるんだ」と煽られました。そら使えますよ。
さらにしばらくして、1年生のserpent君が到着したので、感動しておー！となっていましたが、自分が名乗るのを忘れており、同期に笑われました。敬語は使えますが、自己紹介はできないみたいです。
人がたくさん集まり、それぞれの部屋で準備を始めている頃、お菓子交換会が始まりました。
自分も先ほど買ったお菓子を渡し、「毒入りです！」とニコニコしながら渡していると、誰もが口をそろえてこう言います。
「AGCのA問題であったよね、懐かしい…」
自分も同じことは思っていましたが、全員で意見が一致するのは、異常集団としか思えませんでした。
コンテスト直前、家から持ってきたリゼロコラボの紫色のボールペンをsuzuken君に見せて自慢していました。反応は暖簾に腕押しでした。
勝負ボールペンの準備も万端なので、国内予選は通過間違いなし！
コンテスト本番
コンテストが始まります。
…問題が見えません。
この流れは去年もやっていたので、特に焦りはありませんでした。
しばらくすると問題が見えたので、bayashiko君はA、suzuken君がB、僕はCを読みました。
C問題は、構文解析ということがわかりました。が、散歩の疲れか、問題文が頭に入ってきません。しばらくぽけーっとして読んでいるフリをしていました。
その間にA,Bが読み終わったらしく、流石に自分も足を引っ張るわけにはいかないので、Cを真面目に読み終えました。
読み終えた感想は「なにこれ？」です。明らかにおかしい難易度の予感がしたので、先にD問題へ移行しました。
D問題もよくわかんないなーと思い、適当に二人に声をかけます。二人とも実装を始めているらしく、僕はC問題に戻りました。
C問題は、数式が木で表現されており、その木をうまくパズルすることで、スコアを最大化する、というものです。
とりあえず、パターンがどうなっているか、手元でこねくり回すことにしました。
が、一行に解法が見えてきません。しばらくは何もわからず、うんうん唸っていました。
すると、突然「やばい…やばい…」という声が聞こえてきました。どうやらbayashiko君のようです。声をかけると、A問題で炎上しているようです。直後、「こっちもやばいです」という声が聞こえてきました。B問題も炎上しているようです。終わった…
とはならず、今日の僕はとても冷静でした。散歩で疲れていただけかもしれません。こういうパターンの場合、3人全員が焦り始めると、誰も消火活動ができないので、自分は一つ一つ解決することにしました。
A問題をまず解決することにしました。bayashiko君に聞くと、コードは書けているのですが何故か実行がうまくいかない、とのこと。問題概要を一度聞きましたが、まぁAだし考察が間違っていることはなさそうだったので、あと10分くらい様子を見よう、ということにしました。bayashiko君はすごく謝っていましたが、僕は問題無い、とニコニコしながら対応していました。結果、suzuken君の対応をしている間に無事に通すことができました。入力ファイルにケースをコピペした後保存し忘れていたらしいです。
このようなミスは誰もが一度はすることですし、アジア通過がかかっているA問題は、確実に・素早く通すことを要求されるため、実は下手なB~D問題より難しい可能性もあります。自分もAを担当していた時はとても緊張していたため、bayashiko君が焦っていたのはとても共感できました。ここで変なイメージを付け、そのままずるずる行く方がマズいので、一旦自力でなんとか通しきる、ということができたのはかなり大きい出来事だったと思います。この世の終わり、といったような死にそうな顔をしていたbayashiko君は、なんとかC問題へと押し付けられ移動していきました。
さて、B問題はというと、考察で少し詰まっているようでした。
問題を教えてもらい、適当に自分の思考フローを垂れ流していると、suzuken君にかけそうな雰囲気が出てきたので、実装してもらうことになりました。しばらくすると、そのまま通り、無事2完することができました。
2完はしましたが、もちろんこのままで終わるわけにはいきません。
C問題は明らかにやばい雰囲気があるので、一度順位表をきちんと確認することにしました。
すると、D問題は数チームが通しているのに対し、Cは誰も通していませんでした。
おとなしく、D問題へいくことにしました。
C問題はbayashiko君にそのまま突破口を見つけてもらい、Dを僕とsuzuken君で片づけることにしました。
D問題は、風船を配る回数を最大化する問題です。
自分は、この問題を思い出していました。
で馬鹿でかいものが2つあると、上記の問題に帰着できるよね～、というと、suzuken君は頷きました。
そのあたりで、3分割をするのかな？という発想が出てきました(馬鹿でかいがあるとき、その2つはそれぞれ1つで1グループ、残り全部を最後の1グループとするあたりから発想が出ていたと思います)。すると、ポールを3つのグループに分けた結果、そのグループの最小値が操作回数となるような並び替えの仕方が必ず構築できることを証明できました。
この内容をsuzuken君に伝え、実装をしてもらおうかなと思っていたのですが、実装方法が伝わりませんでした。ので、自分が実装することにしました。
実装はとても軽く、そのままACすることができました。
終わってから話をしたところ、suzuken君はそもそも問題を誤読していたらしいです。通りで話がかみ合わないわけでした。
さて、ここまででA,B,Dの3完です。もちろんこのままで予選が通過できるほど甘いとは思っていません。僕がD問題を通してる間に、2人がC問題を整理してくれているようでした。そこで、実装が比較的得意な僕とsuzuken君はC問題へ行き、その間にbayashiko君はE問題でエスパーを狙う、という方針を立てました。
どうやら、が書かれた頂点は全て根になり得るらしく、また、頂点ごとに繋がっている辺は切れたり加わったりすることはありません。なので、あとはminmaxでDPをした後、全方位木DPをすればよい、ということになりました。
構文解析パートをsuzuken君にお願いしようという話もありましたが、お互いの実装をすり合わせるのが難しそう、ということになり、自分が実装をすることになりました。
実装中、「マジ？」「助けて～」「こんなのおかしいよ～」「ほんとに？」といった独り言を無限につぶやいていました。うるさくてごめん。
実装を完了すると、149行の壮大なコードができあがりました。
コンパイルをすると…なんと通ります。サンプルを試すと…なんと合います。
suzuken君に出していい？と聞くと、OKが返ってきたので出します。
すると…ACしました。バグ無しで通せたのは、我ながら天才だと思いました。褒めてくれる方、募集中です。
僕「やっぱりおかCよ…」
bayashiko君「ダジャレですか？」
僕「し～っ！」
4完して順位表を見てみると、ぽつぽつE問題が通されていました。
Eに取り組んでいた2人に話を聞くと、考察が終わってあとは実装するだけ、という状況らしいです。4完でも通過できるかなー、とは思っていたのですが、確実に突破をしたいので、真面目に取り組むことにしました。
コードはある程度できていましたが、かなり複雑で、デバッグ役として自分が参戦するのは難しい状況でした。そのため、スペアとして、1から実装を行うことにしました。
そして、3人で同時並行で実装する時間が始まりました。
ACしたのは、bayashiko君でした。
bayashiko君はダイクストラ法をライブラリとして持っているため、ソラで書くことができないと聞いていました。
聞いていた情報と違うんですけど！！(歓喜)
bayashiko君がテストケースを通すとき、明らかに手がプルプル震えているのが見えました。緊張するの、わかります。
5完すると、なんと20位以内に自分のチームの名前が書いてありました。
この後、3人とも問題文が頭に入ってこない、と言い訳しながら感想戦をしていました。
UHISHIROを始めとする他のチームが5完すれば3チーム出場できる可能性もあったので、ひたすら祈り続けていました。
コンテスト結果
5完で、16位になりました！考え得る最高レベルの結果をたたき出すことができたと思います。早稲田の学内では2位だったので、その点のみ悔しいです。
コンテスト後
ラーメンを食べに行きました。自分が高校の頃から通っている、一番好きなラーメン屋です。
帰り道、1時間電車で浮かれていました。
同期が集まっているdiscordで聞き専になりながら通話に入っていたのですが、眠くなったので落ちる、といい落ちました。
しかし、気づいたら順位表を眺めており、1時間ニヤニヤし続けました。はたから見たら変な人だったと思います。
家に着き、カバンの中身を整理していると、大事なものが見当たりません。
なんと、リゼロコラボの勝負ボールペンを部屋に忘れていました。
エミリアたん…
思ったこと(おわりに)
正直なところ、自分の競技プログラミングに対するモチベーションは万全と言える状態ではありませんでした。去年、予想外の大敗をして、立ち直るのに時間がかかりました(表面上は元気そうに振舞っていた気がしますが)。自分の周りには、かつて一緒に競技プログラミングに取り組んでいた同期がたくさんいました。しかし、今もまだ続けている人は自分一人です。後輩がたくさん頑張っているのを目にしていましたが、どうしても、競技プログラミングに力を入れられない自分がいました。
今年の6月になって、suzuken君とbayashiko君にチームを組んでもらうことを快諾してもらいました。その直後あたりは、少しだけ精進をしていた気がします。
当初、ライバルチームのメンバーを含めたAOJ-ICPCのランキングでは、自分がダントツTopになっていました。しかし、最終的には、自分はTop争いのレースからかけ離れた位置にいました。
また、自分は一時期競プロにおける自信を失っていました。9月のABCでは水パフォ相当の順位、さらにはARCで0完をし、レートを100失いました。
それでも、チームメイトは一緒に練習をしてくれていました。
加えて、同期の多くが、応援し続けてくれていました。時には僕のブログをネタにされたり、冷やかしを受けている日もありましたが、なんだかんだでAtCoderの順位表を見てくれていたり、最近の調子を聞いてくれたり、激励の言葉を添えてくれたりしていました。
本番中、チームメンバーがピンチな状況になった中でも、自分が常に冷静でいられて、最高のパフォーマンスを発揮できたのは、こうしたまわりの支えがあったからこそだと思います。
また、早稲田の競プロdiscordでは、2018年度で世界大会に通過した、yamadさん、imulanさん、ryoissyさんが通話で応援してくださっていました。コンテスト後、まずここへ報告しに行き、お祝いしてもらったのはとても嬉しかったです。今回、かなりいい順位が取れたので、少しでもこの先輩方に近づけたのかなと思っています。少しでもアジア予選でいい順位を取れて、あわよくば世界大会に…今の実力のままでいけるのでしょうか？
同期とdiscordで通話しながら今こうしてブログを書いていますが、改めて通過できたのだと思うと、今にも泣きだしそうになってしまいます。泣いたら確実に笑われるので、絶対に声は出しませんし、直接応援ありがとうとも恥ずかしくて言えないです(実は応援してませんって日にはこの世の終わりが来ます)。今後も応援してくれたら嬉しいです。頑張ります。
改めて、(まだ正確には確定していませんが)アジア予選に通過できて、本当に良かったと思います。2019年、アジア予選でも大敗しているので、その借りを返しに行かなければなりません。まだまだできることはあるので引き続き頑張って行こうと思います。
ここまで読んでいただき、ありがとうございました。
