ICPC国内予選 2021 参加記

2021/11/05に開催された国内予選にチームAobayama_dropoutで参加しました。模擬国内予選の参加記でも書きましたが、今年のメンバーはゆきのんさん・ha15さん・僕です。

今年は全チームがサークル顧問の先生の研究室に集まれて、3部屋に3チーム・3チーム・1チームという感じで割り振られました。

コンテスト前

当日の午前1時に起きたりして生活リズムが大変でした。細切れの睡眠を繰り返して、最終的には午後2時になってしまいました。部屋割りのために各チーム1人は午後2時半に青葉山にいる必要がありましたが、これをチームメイトにぶん投げて、ゆっくり準備して家を出ました。主な持ち物はノーパソ、キーボード、マウス、蟻本、考察用紙と筆記具です。

例年C問題に重めの問題が配置されており、それより先にDを通すことが多かったので、今年は僕がC問題を読むことにしました。リハーサルは手付かずでしたが、さすがに4年目なので大丈夫でしょう。一応問題だけ見ましたが、これも例年通りでした。

研究室にあったモニタを1台拝借して、一人だけデュアルディスプレイにしました。増やした画面にはチームで共有したいページを開いておくつもりでしたが、結局、たまに順位表を見るだけにしか使いませんでした。

コンテスト中

問題文:

icpc.iisf.or.jp

今年も、最初しばらくページが見れない状態が続きました。両隣のチームメイトが問題文を開けてからも、僕のブラウザはずっと応答待ちを続けていました。向こうのサーバーの問題だと思ってそのまま待っていたのですが、F5を何度か試してみるとか、テザリングに切り替えるとかしてもよかったのかなと思います。5分くらいしてトップページが開けたので、問題文pdfへとアクセスしたのですが、そこからもさらに読み込み時間がかかりました。

C問題

C問題の読み込み途中で止まってしまったのでリロードしたところ、やっと文面が読めるようになりました。画像はまだ読み込めておらず、文章を読んだ感じは画像がないと理解に手間取りそうだったので、先にD問題をチラッと見ましたが、よくわかりません。C問題に戻って、画像のキャプションから手作業で図を復元していましたが、ゆきのんさんに言われてページをリロードしたところ、今度こそ画像ごと読み込むことに成功しました。

特殊な形をした構文木を操作して値を最大化する問題のようです。許されている操作はちょっとややこしかったですが、どうやら根をその子に取りなおしたり、子の順番を入れ替えたりすることが可能なようです。葉でない任意の頂点を根に持ってくることができますが、このとき残りの木は子の順番を入れ替えるだけの自由度しかないのではないでしょうか。直感的に正しそうで、これを認めればあとは全方位木dpするだけなので、深く考えず実装に入りました。コンテスト後に知ったことですが、ノードたちの接続関係が変わらないことから言えます。

構文解析して構文木を作る部分では、一瞬構造体のポインタを考えましたが、そんなのは嫌なので頂点番号を振って配列と隣接リストで持つことにしました。全方位木dpでは引き算の頂点の処理が面倒でしたが、次数が3で固定なので全通り書き下しました。

コピペを駆使して実装し、サンプルを試すと合ったので、そのまま提出し、無事ACを得ました。ha15さんに言われて気づきましたが、CのFAだったようです。しかし、開始からすでに30分が経過し、Cの代わりにD問題が大量に通されていて、びっくりしました。

D問題

僕がコーディングしている間にチームメイト2人はそれぞれABを通し、Dに進んでいたので、僕も合流します。正直、こんなたくさん解かれているんだから真面目に一瞬考えれば解けるだろうと思っていました。しかしなかなか思いつきません。

とりあえず、サンプル3つ目の5 2 8 3でなぜ風船を配り切れないかを考えることにしました。サンプル1つ目の説明から、どうやら最初に風船が多いポールを置くのがよさそうだったので、とりあえず8を先頭に持ってきてみます。すると残りは52+3に分割するのが最適で、8-5=3個余ってしまうようでした。つまり、どれかのポールに特別風船が多いときは、それ以外のポールを2分割するのがよさそうです。2分割の場合の解き方は、要素を順番に見てdp[i][j]=iとjに分割できるかどうかというdpになります。

そういうようなことを棒を積み上げる図を描いてゆきのんさんに喋っていたら、3つの場合は3分割でdp[i][j][k]のようなことをすればよいのでは?と言われました。確かにそうです。実装もゆきのんさんに任せることにしました。i+j+kが風船の個数の総和になるので、dp[i][j]でよく、これでちゃんと時間内に終了するdpが得られます。

E問題

D問題の実装を横から見つつ、haさんと一緒にE問題を読みましたが、題意を頭に入れたあたりでD問題の実装がひとまず完成していたので、考察を放り投げてデバッグの様子を眺めたり口出ししていました。

E問題に対する自分の直感として、車道で連結成分に分けてそれぞれで拡張dijkstraするというものがありました。これをha15さんに話しつつ、連結成分を何度も行き来するようなケースがあるかもしれないと考えていたところ、ある程度以上タクシーを乗り降りする場合はできるだけ回数を減らすように動いていいのではないか、ということをha15さんが言い出しました。正しそうです。

適当なしきい値を定めて、タクシーを待つ回数がそれ未満の場合は拡張dijkstraで、以上の場合はタクシーを待つ回数と経過時間をペアで持ってdijkstraをします。しきい値としては、距離が最大で2\times 10^{10}くらいになるので、これを待ち時間が越えるくらいで定めればよさそうです。実装をha15さんに任せて、F問題に進みました。

F問題(解けず)

Dを通したゆきのんさんとF問題を読みます。作ったグラフの各辺がありうる最大マッチングのうちどれかに含まれる、という言い換えは、すぐ元の問題に戻ってきてあまり筋がよくありません。見切りをつけるまでに、すでにかなり時間を使っていました。

1つ最大マッチングを固定して、それに含まれない辺を使おうとしたときどのようにして新たな最大マッチングを作成するかを考えることにしました。増加道のようなものを考えると、今指定した辺を含み、最大マッチングに含まれる辺と含まれない辺を交互に通るような閉路が存在すればよいです。

最大マッチングで結ばれた相手の頂点から、ほかに(最大マッチングに含まれない)辺が出ている場合、自分も1本以上辺を持つ必要があります。実はこの条件だけで、サンプルで新しく辺を張る頂点は検出しきれます。なので、それらをうまく繋ごうとしましたが、2つ目のサンプルの繋ぎ方は1通りしかないようで、これがなぜなのかがわかりませんでした。また、2つ目のサンプルにさらに2 14 3という辺を足すことで、先ほど述べた条件を満たさない頂点からも辺を張る必要があるケースが作れてしまいました。

確か上の考察の途中あたりで、E問題が書きあがっていました。サンプルを試したところ出力が合っていたので、提出してもらいましたが、WA。急いでコードを共有してもらって眺めていると、コスト計算にミスを見つけたので、そこを修正してもらって再度投げなおすとACでした。サンプルに、そう何回もタクシーを待つケースが含まれていないのは考えてみれば当然のことなので、焦って投げる前にチェックさせてもらえばよかったです……。

F問題の考察に戻ります。ここで僕は二辺連結成分分解を考えました。橋となるような辺ができないようにうまく辺を張れればよいと思ったのです。二辺連結成分分解した後の木の葉たちを繋いでループを作ります。そのようなことが可能かはちょっと怪しいですが、可能ならば木dpの要領で作れるはずでした。残り時間も10分くらいになったので、とりあえず書き始めてはみたものの、全然書きあがらずコンテストが終了してしまいました。

コンテスト後

購買でお菓子を大量に買い込んでおいたのですが、まったく手を付けませんでした。封が開いていないものはチームメイトで分け、そうでないものはその場で食べていたら、他のチームが続々と帰って行きました。僕個人としてもあまり元気がなかったので、チームでの打ち上げはしないことにして、解散しました。

振り返り

結果はABCDEの5完で、全体8位、学内2位でした。

icpc.iisf.or.jp

まさか自分が学内1位から転落するとは、と愕然としています。序盤10分くらい問題文が読めなかったのに余裕ぶっこいていたのは明らかによくありませんでしたし、DもEもわかってみればあまりにも明らかな解法なので、見た瞬間解けるべきでした。

Dとsolved数の逆転が起きていたCを僕が解いたのは良かったです。また、戦略としてみれば、DとEをチームメイトに割り振ってF問題の考察に専念しようとしたのは、いかにもチーム戦という感じがして良いはずでした。

しかしこの戦略は僕がF問題を解けることが前提になっており、実際は2時間くらい考えていたのに解けなかったので、台無しになってしまいました。上に書いた考察で正しく進めているのは増加道の下りまでで、このとき辺を向きづけてループが必ず増加道となるようにするのが正しい道筋だったようです。この場合二辺連結成分分解ではなく強連結成分分解が出てくるそうです。

最近まともな精進をしていないので、横浜までにはまたAOJ-ICPC埋めを進めておきたいです。