再開して初めての AGC ですね。今回は A の 1 完でした(165:04 + 50:00)(10WA)。 色々試行錯誤をして解けたのは嬉しかった。 まあレートは下がったけれど、通せたのは大きいと思う。 AGC で青 Diff がコンテスト中に解けるのはかなりいいのでは。
曖昧になっているところを詰めきれずに結構時間がかかったのとかなり WA を出してしまったが、 解けた。
まず、証明ができていないのだが、ある数を選んだ後に次に選ぶ数というのは、 それよりも小さい最大の値に限る。なおそれがない場合は選んでないものの中で一番大きいものになる。 できるだけループの数(ある値を増やして $K$ になったら $0$ に戻すみたいなのを $1$ ループというのならば) を増やして置いていくのが理想的なので、そのような置き方ができれば最も多くループさせることができるという 考えでいいのかな。
すると、ある値から始めてシミュレーションする解法が一応出来上がる。これは $O(N^2)$ である。 そうしたら、これを速くする必要があるのだが、これは差分を考えると速く解ける。
もし一番大きい値を最初の値にするのならば、降順に走査して、残ったものをまた走査して、というのを繰り返すと思う。 この時どういうデータの構造を持ちたいかと言うと、$h$ 回目にアクセスする値たち $v_{h, i}$ みたいな物をつくる データの構造を持っておけばやりやすそうである。それらは $h$ ごとに降順になっている。
そして、次の値を最初の値にしたいときに、先程の一番大きい値を持っている $v_{h, 0}$ を末尾に移動すると、 再び走査できる形になる。しかし、この時値が変化している部分というのは、$h$ 段目の値から $h+1$ 段目の値に移動するところについてであるので、実はならしで $O(1)$ で処理できる。 このように、$v$ についてうまく先頭を末尾に移し替え、差分を計算すると、$O(N)$ で処理できることがわかる。 先頭から末尾に移動させるようなものは deque を使うとうまく実装できる。
ソートに一番時間がかかるので $O(N \log N)$ である。
ある程度解法を理解できたら実装しにかかるのだが、途中で細かいところを詰めきれていないことが発覚して まず実装自体がとんでもないことになっててバグの直しようがなかったりするので一回それで提出してみるかとなり、 WA を出し、もっと簡単な実装方法を見つけて書き直すなどしていたら時間がかかった。 ただ、3 時間コンテストに救われた。
Perf = 1606 だった。慣れてない AGC にしては悪くない結果だとは思う。
時間を掛けて解けるならば、後はそれを速めるだけなので、解けたのはかなり大きいと思う。 3 時間もあると考える時間も長くなるが、できるだけ手を動かすことで堂々巡りも回避できたので、 立ち回りとしては悪くはなかったかなと思った。
(2023/12/18 01:41)