ICPC2021国内予選参加記

予選以前

去年まででふぇりんさんが引退してしまったので今年からはなーぶ君が加入して新生nowcowとして生まれ変わった。

なーぶ君には幾何とフロー実装できるようにしといてくれ！と叫んでいたらAOJの幾何の基礎のやつ(？)とか埋めていてえらかった。 でぃぶ君には去年まで構文解析とかの実装をやってもらっていたので、僕もデータ構造頑張るか～って言っていた。アジアまでには頑張ります……

模擬国ではなーぶ君に全方位木DP投げてもよさそうであることが分かったので嬉しくなっていた。考察をしたいので。

国内予選

でぃぶ君A なーぶ君B おるふぇCで開く。Ｃを開くとかなり難しく&重く見えてかなり焦る。でぃぶ君がAを通してしばらくしているとBで2ペナ生えてるのが見えたのででぃぶ君にCを押し付けてBの話を聞きに行くと、かなりよくわからないことを言っているように聞こえたので、僕が書きますと言う。 書いているとペナが増えていて焦るが、4ペナで通す。途中でペナが20分であることを説明する(ごめん……)

CはやりたくないのでDとEを見るが、Dはひらめき系に見えてひらめかなかったのでEを考えると、タクシー乗る回数を少ない範囲では全探索して多い範囲では最小化すればいいことが分かるので正しいことをなーぶ君に軽く確認して実装を始める。そのころでぃぶ君はCが解けたらしく、Cの実装を始める。途中誤読に気づいたが、修正して提出するとWAが出る。なーぶ君とデバッグしていたが、何点か修正しても古い出力と変わらないのでかなり焦っていた。ここまでで2時間ぐらい経過していて140位とかで2度目の予選落ちが頭をよぎっていた。あまりにも苦しくなってきたので変わってないけど出すか！って言って出すと(？)通る。その30秒後ぐらいにでぃぶ君がCを通し、一気に20位ぐらいまで上がりお祭りになる。僕はこれで予選は通過したかな～とか言っていた。安心したので冷静さを取り戻す。

Dについて考えると最初の3要素の順番はどうでも良いことが分かり、実験をするとサンプル2は以下のような順序のみ条件を満たすことが分かる。

1 3 3 4 3 3 4 3 3
3 3 4 3 3 1 4 3 3
3 3 4 3 3 4 3 3 1

なんとなく3組に分かれている気がしたので投げると通る。通ってから正当性は理解しました。

残りの時間は分からないFGHを考えていた。

結果は5完21位で国内予選通過でした！同校から参加していたATELIERも通過していたので一緒にアジアまで頑張ります。

反省

順位表を見てBの様子を聞いたのは良かったが、Cに対してしたのは多分邪魔なだけだった。難しすぎる……

古い出力をちゃんと取っておく。

落ち着く(どうやって？)

その他

九死に一生を得たという感じで非常にしんどかった。

めっちゃ人々を冷や冷やさせていたらしい。僕が一番冷や冷やしていましたけど。

ちなみに4完で終わっていると予選落ちです。危なかったね。

でぃぶ君にも全方位木DPを投げていいことが分かった。嬉しいね。

ちょくだいさんへ AtCoderで沢山問題解いてるのにひやひやさせてごめんなさい。