問題概要
以下の条件を全て満たす長さ $l+1$ の数列を 入力列 と呼ぶ。
- 先頭の項が $l$ である。
- それ以外の項は何でも良い。
入力列の例: (3,1,4,1),(1,100),(5,2,3,52,23,523),(0)
以下の条件を全て満たす数列を マルチテスト列 と呼ぶ。
- 先頭の項が $x$ であったとする。
- それ以降の項は入力列を $x$ 個繋げたものである。
マルチテスト列の例: (1,3,1,4,1),(2,1,100,5,2,3,52,23,523),(3,1,4,1,5,9,2,6,5,3,5,8,9,7,9),(0)
長さ $N$ の数列 $A$ が与えられるので、 $A$ の suffix のうち長さ $2$ 以上のもの全てについて以下の質問に答えよ。
- suffix の要素を最低何個変更すればそれをマルチテスト列に出来るか？
制約
$2 \le N \le 300000$
$1 \le A_i \le 300000$
ひとまず、最大 $2$ 変更で必ずマルチテスト列にできることを示す。
長さが $l$ の列について、先頭 $2$ 項を $(1,l-2)$ としてしまえばよい。
ここで、以下の問題が解ければよいことになる。
- 変更なしでマルチテスト列かどうかを判定する
- $1$ 変更でマルチテスト列にできるか判定する
変更なし側から解いていく。入力列を一塊と見てダブリングすれば解けるが(本番中に引いて間に合わなくなった)ハズレ方針なので別の方針で進める。
実は、以下の $dp=[$ suffix の先頭 $]=\{$ 入力列の個数 $\}$ をすればその結果から解ける。
- $dp[N+1] = 0$ 、それ以外 は $dp[i]=-1$ と初期化する。
- $i=N,N-1,\dots,1$ の順に以下を行う。
- $pt=i+A_i+1$ とする。
- $pt>N+1$ なら $dp[i]=-1$ である。
- そうでなくとも $dp[pt]=-1$ なら $dp[i]=-1$ である。
- そうでないとき、 $dp[i]=dp[pt]+1$ である。
このとき、 $A_i = dp[i+1]$ であることが $A_i$ を先頭とした suffix が無変更でマルチテスト列であることの必要十分条件である。
これで変更なし側は解けたので、 $1$ 変更の場合を処理していく。
こちらにも場合分けがあり、
- 初項のみが誤っている
- 初項以外のどこかが $1$ 箇所だけ誤っている
の $2$ 通り。
初項のみが誤っている場合はさっきの $dp$ が活用できる。
$A_i$ を先頭とした suffix について、 $dp[i+1]$ が $-1$ でないとき、 $A_i = dp[i+1]$ と書き換えれば $1$ 変更でマルチテスト列とできる。
初項以外のどこかが誤っているパターンが最難関だが、これも DP でどうにかなる。
$dp 1[$ suffixの先頭 $]=\{$ $1$ 変更以内で作れる入力列の個数の最大値 $\}$ を考える。これは以下のように解ける。
- $dp 1=dp$ と初期化する。
- $i=N,N-1,\dots,1$ の順に以下を行う。
- $pt=i+A_i+1$ とする。
- $pt \le N+1$ かつ $dp 1[pt] \neq -1$ なら、 $dp 1[i]$ に $dp 1[pt]+1$ を遷移する。(いじらなくとも遷移できる部分)
- $dp 1[i]$ に $\max(dp[i+1],dp[i+2],\dots,dp[N+1])+1$ を遷移する。(うまいこと $A_i$ をいじったら遷移できる部分)
$A_i$ を先頭とした suffix について、 $A_i \le dp 1[i+1]$ なら $1$ 変更でマルチテスト列とできる。
丁度 $A_i$ 個の入力列を作るのが目標だが、適切な場所を適切にいじれば最大値以下ならいくらでも入力列の数は調節できる。感覚としては複数のテストケースをいい感じに橋渡ししたり、必要なケース数が集まったら強制的に末尾まで持っていったりする感じ。
(2,1,4,3,5,3,1,4,1,2,4,3) を (2,1,4,8,5,3,1,4,1,2,4,3) にいじったり、 (2,1,4,999,1,1,1,2,7,7) (破損) を (2,1,4,3,1,1,1,2,7,7) なり (2,1,4,1,1,1,1,2,7,7) なり (2,1,4,6,1,1,1,1,1,1) なりにいじるみたいな具合。
これを全部実装するとこの問題に正解することができる。
Submission #199313409 - Codeforces
題材も解法も美しい良問。できればコンテスト中にスパッと解いて間に合わせたかった…
