APIO2021 参加記 - SSRS の競プロ日記

APIO2021 に参加しました。

競技

Hexagonal Territory を読む。六角グリッドでやばそう。とりあえず Territory (難易度 11) を思い出すがよくわからない。9 点の部分点は数学で簡単に取れそうなので取る。Rainforest Jumps を読む。4 点が自明なので取る。8 点もワーシャルフロイド法をするだけなので、取る。Road Closures を読む。5 点が自明なので取る。7 点も簡単な DP なので取る。

簡単そうな Rainforest Jumps に戻る。小課題 3 の 13 点は距離の配列が得られるので長方形領域の最小値を求めることに帰着。簡単な解法が思いつかなかったのでセグ木を書く。セグ木を 2000 本持たせる $O(N ^ 2 + QN \log N)$ を投げる。log が付いているので若干不安だが、通った。

小課題 4 を見る。 $Q \leq 5$ なのでそれぞれの樹から飛び移れる樹を stack を使い $O(N)$ で取得し、BFS でクエリに答える。コードを投げるが、なかなかジャッジされない。ジャッジキューが詰まっているとの連絡が来ているので、とりあえず別の問題に移る。

Hexagonal Territory の小課題 3 は BFS で解けるとわかっていて実装を後回しにしていたので、実装をして投げる。提出欄を見ると、なんと今までに投げたすべての提出が WJ 状態に戻っていて、リジャッジが行われているとの連絡が来る。このあたりで開始から 1 時間経過。

Rainforest Jumps に戻り、小課題 5 を解く。貪欲に高いほうの樹に飛び移る戦略がだいたい正当なので、ダブリングを実装して投げる。Rainforest Jumps の小課題 3・4 はどうせ次数を持つ木 DP なので、適当に $O(N ^ 2)$ を実装し投げる。なかなかジャッジが返ってこないので clar を投げる。ジャッジ詰まりの影響でコンテスト時間が 30 分延長になるとの連絡が入る。

残りの問題を考察するが、よくわからない。コンテスト開始から 2 時間経過。ジャッジ詰まりのため各問題に 5 分に一回の提出制限がかけられるとの連絡があり、不安になる。

しばらくして、ジャッジが返り始めるので眺めると、投げた提出が何個か落ちているので確認。Rainforest Jumps の小課題 5 が落ちているので適当に修正し投げる。Hexagonal Territory の愚直 BFS も落ちたので確認すると点数の計算方法を誤っていたので、計算を修正すると通る。Road Closures の木 DP も落ちているので確認すると誤解をしているので直す。コンテストがさらに 30 分延長されて 6 時間になり、提出制限が元に戻る。

Hexagonal Territory と Road Closures は通ったが、Rainforest Jumps が通らないので、ワーシャルフロイド法の結果と比較するランダムチェッカーを書くと、貪欲をすると超えてしまう状態の後に二回以上移動する必要があることがあることを見落としていたことに気付き、右方向への移動だけでのダブリングを別に持ち、いろいろデバッグをすると通る。小課題 6 は二分探索で簡単に小課題 5 に帰着するので、実装。満点も取れそうなのでいろいろ考察し、何回か WA を出しながらなんとか通す。コンテスト開始から約 4 時間が経った。

Hexagonal Territory は自明な小課題以外の得点を取れていないので、面積を求めればよい。ピックの定理のようなものが使えるのではないかと気付き、実装をする。Road Closures の小課題 5 も考察する。マージテクをしたり、木の次数 $d$ の頂点の個数が $\displaystyle{O(\frac{N}{d})}$ 個であることの利用を考えるが、解法にはたどり着けず終わった。結果は 47+100+38=183。木はどちらかというと得意な分野なのにあまり点数が取れなくて少し悔しい。

終了後

人々の得点を見る。KoD さんと blackyuki さんが Road Closures で満点を取り 200↑ の得点を得ていた。すごい。

結果が発表される。得点は日本 3 位で銀メダルらしい。