AGC036 B - Do Not Duplicate - ツバサの備忘録

解法

同じ状況になる部分をどんどん取り除き、最終的に残る数回を愚直にシミュレーションします。
まずは、空の数列 $s$ に対して $i$ 番目の数字 $A_{i}$ を $s$ に入れたときに、 $A_{i}$ を取り除くことで再び数列が空になるタイミングはどこか、を調べます。
これは、 $A_{i}$ の種類ごとに $i$ を昇順にまとめ、 $i$ に対しては $A_{i} = A_{j}$ となるような、 $i \lt j$ となる $j$ のうち最小の物をメモすればよいです(もし存在しなければ、 $A_{i} = A_{p}$ となる最小の $p$ をメモします。 $i = p$ となることもあります)。
次に、初期状態( $s$ が空の状態で、次に挿入するものが $A_{0}$ であるタイミング)まで一回ループするのに何回操作をするか、を調べます。
これは、次に操作する数列の番号 $i$ を最初に $i = 0$ とし、先ほどのメモを見ながら、数列が空になるタイミングごとに区切って調べていけばよいです。
$i$ に対してのメモが $j$ の場合、 $j - i + 1$ 回操作を追加すると数列が空になり、次に操作する対象は $j+1$ 番目になります。ので、操作回数に $j - i + 1$ を加算し、 $i = j + 1$ と再定義します。ただし、 $i \geqq j$ の際は、 $j - i + 1 + N$ となります。
これを、再び $i = 0$ となるまで行います。
メモの種類はもちろん添え字 $i$ の分だけなので、これは最悪でも $N$ 回の操作となります。
$s$ が空かつ、 $i = 0$ で操作を開始して、再び同じ状態に戻ってくるまでの回数を $L$ とします。すると、操作をする回数 $NK$ は、最終的に $NK \ mod \ L$ となります。これを、新たに $K$ と定義しなおします。
この時点での $K$ は、最大で $N^{2}$ 程度です( $A_{i}$ が全て異なるパターンです)。
ここから、さらに値を減らします。
先ほど、1回ループするまでの回数をシミュレーションをしましたが、これと同じ操作をしつつ、今度は $j - i + 1$ を $K$ から直接減らしていきます。そして、 $j - i + 1$ を減らすと $K$ が負になる、というタイミングでやめます。このシミュレーションは、先ほどと同じく最悪でも $N$ 回の操作で済みます。
こうすると、残っている操作回数 $K$ は、最大でも $N$ となります(次に操作する添え字を問わず、数列が空の状態から再び空になる際の最悪ケースは、先ほどと同じで $A_{i}$ が全て異なるパターンだからです)。
ということで、操作回数を $N$ まで減らすことができたので、あとは現状の $i$ から愚直にシミュレーションをしていけばよいです。
これは、stackを使うと、最大で $2N$ 回程度のプッシュ、ポップの操作になるので十分間に合います。すでにスタック内に存在するかどうかは、setを利用しました(こっちの方が計算量的には重くなると思います)。
計算量的には、おそらく $O(N log N)$ です(自分は最初の $A_{N}$ ごとにまとめる操作を行う際にc++のmapを使用したため)。

感想

ループをするのでその部分をどんどん減らす、という発想が割とはやいタイミングでできたので良かった…です。