ICPC国内予選2021 参戦記 - sapphire15の日記

torisasami, tokusakurai とDELIAIR としてICPC国内予選2021に参戦しました。結果は全体17位、学内6位で（正式発表はまだですが）残念ながら予選通過はなりませんでした。

開始前

discord で通話しながら参戦。何回もチーム戦をしているので慣れてはいる。

とりあえず A : sapphire15 B : torisasami C : tokusakurai ではじめることに。

予選中

A

問題文が長い。読解に時間がかかった。一気にすべての器が空になるパターンない？と思ったけど選んだ器は減らないのでそんなパターンはない。これで少し手が止まってしまって、その間に torisasami が B を通してしまった。なんだかんだで7分位でAC。

C

構文解析らしいがtokusakurai がそのあとがよくわからないらしいのでヤバそう。全方位木DPでできそういう話はこの時点で出てたけど、さすがにCに出すか？という話になって実装しようとしなかった。

自分が構文解析担当と事前に決めてたのでのでとりあえず構文解析を書いて構文木を作るところまでやる。その間でも簡単な解法は出ず、順位表を見ても誰もCを通してないということでDに行く。

D

ぱっと見できそうに見えるけど３人で話してもよくわからない。かなり焦る気持ちも出てきたので心を落ち着かせるために E を見る。

E

最初にタクシーを使う回数が大体40回以下だからそれで拡張ダイクストラするという解法を提案するが、必ず歩道が使えるわけではないので２人に撃墜される。そのあとすぐに、tokusakurai がタクシーを乗った回数を優先的に見るダイクストラもすることを提案して良さそうなのでそのまま実装はじめる。（天才）ここまで10分なかったと思う。

D 再び

ここでもう一度 D を見ると解法が降ってくる。

使う棒を入れ替えるときに入れ替えたもの同士を1つのグループとみれば、全体を３分割できる。このとき３つのうち最小のものが風船を配ることのできる子供の数になる。あとは２次元DPであらゆる３分割ができるどうかを判定すればいい。

解けたので自分が実装をすることに。 torisasami も同時にCの全方位木DPを書くことになった。

D は結構バグらせたけど複雑な実装ではないので通る。開始36分くらいだったらしい。ここらで5完のチームも出てきて5完しないと予選通過は厳しいかもしれないという雰囲気がでてくる。

F, G

2人の実装を手伝うのも難しそうなので F, G を眺める。 F は問題文を説明すると実装中の tokusakurai が DM分解っぽいと言う。 DM分解をググったけどよくわからなかったので、一旦スルーする。

Gは頑張ってbitDPすれば行けそうに見えるけど、詳細を詰めるのが大変そう。個人的には F よりかは希望がありそうに見えた。

結局 30分くらい2人のサポートに回る。テストケースの解析をしたり、テストケースを作ったり。結局ここでたいした貢献ができなかったのでちょっともったいなかったかもしれない。

Eは問題を勘違いしてたみたいだけど2ペナしながらも修正して通す。そのあとすぐに C も合わせることができたみたいで通して5完。（まあまあな重実装だったけど2人ともさすが）

F, G 再び

順位表を見る限り完数勝負にしなければ厳しそう。 F はtokusakurai が結構見えてそうなので torisasami と解法を詰める。

一方で自分は G を頑張ったらできそうにみえたので予選通過のオッズを上げるためにも G を担当することにする。

G は縦列の通路でランプをおかなければならないものを保持しながらbitDPすればよさそうなんだけど、横列も見なければいけないし単純ではない。残り30分くらいで解法を詰めて実装にかかる。（終ったあとに嘘だったことがわかった（悲しい））残り5分で実装し終わるけど当然サンプルが合わない。すると、tokusakurai がFが合いそうと言う。残り1分でtestcase1を通したらしい。行けるか？と思ったが、、、

残念ながらtestcase2でWAが出て終了。

感想、反省

悔しい結果となってしまいました。問題は全体としてやや難しいセットですが一問一問はいい問題だっただけに残念です。

敗因ですが、個人的には実力不足はもちろん精神面にもあると感じました。

正直なところ開始前から浮き足立っていた感触はありました。*1 そこにC, Dで詰まったことが加わり、チーム全体としてあまり冷静になれていなかったように感じます。実はそのような展開になる可能性があることを予想はしていましたし、そのため競技中の声かけを意識したつもりなんですがオンラインということもあってなかなか難しかったです。*2

その他、全体としての立ち回りなど反省はつきないですが終ったことですし一旦ここまでにしたいと思います。