CODE FESTIVAL 2016 qual A: E - LRU パズル / LRU Puzzle
解法
素直な感じでやって $O(N + M + Q)$ で解ける。
まず、目標通りに $N$ 個の数列を構築できたとするとそのような数列 $b$ がどのようになるかを考える。 この $b = (b_1, b_2, \dots, b_N)$ は (もし存在すれば) 一意であることが示せる。 明らかに $b_1 = a_Q$ であり、$a _ {Q-1} \ne a_Q$ なら $b_2 = a _ {Q-1}$ であり、$\dots$ と考えればよい。 つまり $a$ を逆順に見て $2$ 度目以降の出現を無視した感じのもの、あるいは $N = 1$ と思ってひとつの列に $Q$ 個の操作を適用した結果が $b$ である。
次に、クエリを自由に捨ててよいかどうかを考える。
これは偽である。
まったくすべて捨ててしまえば答えは自明に Yes
になるが、そうでないため。
しかし、もしクエリ $i$ 以降で同じ値 $a_j = a_i$ のクエリ $j$ があるなら、クエリ $i$ は捨ててよい。
これはクエリ $i$ を、クエリ $i$ を用いる予定の列に対し適用すればよいため。
数列 $b$ の末尾の単調増加連続部分列 $d$ について考える。 たとえば $M = 6$ かつ $a = (1, 3, 6)$ なら $b = (6, 3, 1, 2, 4, 5)$ であれば suffix $d = (1, 2, 4, 5)$ がそれである。 これらの部分については、もしその手前 (上の例では prefix $c = (6, 3)$) を一致させられるならばこれも必ず一致させられるので、無視してよい。 このことは $a$ 中に含まれない数 (上の例では $2, 4, 5$) については明らかである。 $a$ に含まれる数についても、$b$ の定義と重複したクエリを捨ててよいことを使ってすこし考えれば言える。
数列 $b$ の末尾の単調増加連続部分列に含まれない部分 $c$ について考える。 いま、この部分について $N$ 個の列を一致させられるかのみを考えれば十分であることが分かっている。 これは列 $a$ を $\mathrm{rev}(c)$ に一致してかつ互いに素な $N$ 個の部分列に要素を余らせることを許して分割できるかどうかを見ればよい。 これは適当な貪欲で判定できる。