2021/03/07に開催された模擬地区予選にチームAobayama_dropoutで参加しました。 メンバーは変わらず碧黴さん・ゆきのんさん・僕です。
模擬国内で使用するユーザ名とパスワードは、各チームに3組ずつ配布されました。直前になって適当に割り当てを決め、コンテスト開始です。
序盤（C問題）
特に何も打ち合わせがないまま、シュッと始まりました。碧黴さんがA、ゆきのんさんがBを読むらしいので、僕はCを読みます。
Cは挿入DPができそうな見た目をしています。同じ値の要素をまとめて、個数を見つつ遷移をしていきます。DP配列としてi<j<kかつa_i>a_k>a_jのうちjだけがある状態、jとkがある状態、すべてある状態、の3つを考えます。1つ目は必ず1通りで、3つ目は値が1種類しかありません。2つ目については、条件を満たすjとkの組のうちjが最も大きいものを考えることになるため、これだけは配列で持ちます。
これで適当に遷移を書いてみたところ、O(N^3)でした。サンプルを試すと一発で合ったので提出、AC。39分で、2番目のACだったようです。
E問題とB問題
僕がCを通している間に碧黴さんがAを通し、D問題の概要を共有してくれていました。パッと見フローですが、どうにもグラフが想像できなかったので、Eを読みます。明らかに牛ゲーなので、碧黴さんに伝えて実装してもらいます。
ゆきのんさんがB問題で詰まっていたので、これも概要を教えてもらい、priority_queueで中央値を動的に管理する方針を立てて伝えます。これは左右のサイズを注意深く観察しないとすぐバグるイメージなので、ちょっと面倒そうだなと感じて細かい実装までは伝えませんでしたが、ゆきのんさんも同様の解法を見たことがあるらしく、伝わりました。
F問題
Fを読みます。円を左右に分けてCHTっぽくやれば解けると考えましたが、ここで嘘をつきました。実際に式を立てればCHTであることがわかるのですが、僕はそうではなく「曲がっていても直線っぽく扱える」と感じてしまい、スライド最小値で実装してしまいました。
ここで碧黴さんのEがREを出したらしく、コードが共有されてきます。見てバグを指摘したところ、またRE。再度見るとまだバグが残っていて、これを修正してもらうとやっと通りました。
またゆきのんさんがBを通し、Iを読んでいるようで、概要が共有されてきます。そのまま期待値DPをする方針も立ったらしく、掃き出し法をするライブラリを提供しました。
さて、Fですが、実装が間違っているのではないかと疑っていろいろ適当に書き換えた結果4WAくらいしていました。さすがに考察を疑い、結果まずいケースを発見しました。ある円をある円が覆っているとき、その2つがqueueの先頭でずっと比較され続けるのですが、その間に下から別の円が上がってくる可能性があります。
結局一から書き直すことになって、CHTという方針そのものを捨て、円をソートして交点を調べ、最大値が変わる境界を保存して、クエリには二分探索で答えるコードを書きました。提出すると一発AC、185分でした。
G問題
僕がFを通すより先にゆきのんさんのIが通りました。そのまま3人でGを読みます。僕はもう全然頭が回っていませんでしたが、ゆきのんさんが半分全列挙を疑いました。その方針で考えてみたところ、右半分を先に列挙して、左の数が10の何乗倍されるかによって保存するテーブルを分ければ、解けることがわかりました。
僕が実装して提出しますが、RE。コードを共有してみると、すぐにREを出すケースが作成されてきました。
123456789123456789123456789123456789 47
どうやらテーブルのサイズが1足りていなかったようです。増やして提出しなおすとAC！243分でした。
残り時間
最後に全員でKを考えていましたが、全然ダメでした。今振り返ってみれば、全然集中していなかった気もします。
結果
12位でした。全体的にあんまり集中できていなかった気がしますが、これはここ数日コードゴルフ大会にどっぷり浸かっていて、睡眠時間などを削ってしまっていたからだということにしておきます。
実装の分担は結構できていたのではないかと思います。