結論から述べると非負整数からなる単調非減少列 \(A\) が「良い数列」である必要十分条件は

• \(Z_i=i\ (1\leq i \leq K-1), Z_{i}=K \times Z_{i-K+1}\) で定義される数列 \(Z\) に対し \(A_i < Z_i\) が成り立つ。
• ある整数 \(i\ (1 \leq i \leq N-K+1)\) が存在して、 \(A_j < j\ (j=1,2,\dots,i-1)\) と \(A_{i}+A_{i+1}+\dots +A_{i+K-1} \leq Ki-1\) が成り立つ

です。

これを認めると最適化部分についてはまず \(A_i\) の値を \(\min(A_i,Z_i-1)\) に変更した後、 \(2\) 番目の条件をみたす \(i\) を決め打ち全探索を行うことで、（累積和など利用すると）\(O(N)\) 時間で求めることができます。

では上が必要十分条件であることを十分性、必要性の順に示します。

十分性

まず \(i\) 項目を先頭とする \(K\) 項に対して操作を行うと、\(A_i < i\) が成り立ち、 \(A_i\) からは同じ値が \(K\) 項連なっています。ここから \(i-1,i-2,\dots,1\) 項目を先頭とする \(K\) 項に対する操作をこの順で行うと最終的に \(A\) の先頭 \(K\) 項が \(0\) になっています。

ここからは \(A\) の \(K,K+1,\dots,N\) 項目の順に一つずつ \(0\) にします。 \(A_1,A_2,\dots,A_{i-1}\) が \(0\) で \(A_i < Z_i\) が成り立つとき、 \(A\) の \(i\) 項目を \(i\) 項目までの範囲内の操作で \(0\) にできることを帰納法で示せばいいです。まず \(i\) 項目を末尾とする \(K\) 項に操作を行うことで \(A_{i-K+1}=\left\lfloor \frac{Z_i-1}{K} \right\rfloor\) が成り立ち、漸化式からこの値は \(Z_{i-K+1}\) より小さいので、帰納法の仮定から \(0\) にできます。 \(i-K+2,\dots,i\) 項目についても同様に \(0\) にできます。以上より示されました。

必要性

まず \(Z_i \leq A_i\) なる \(i\) が存在する場合、どのように操作しても、操作後もそのような \(i\) が必ず存在することが、 \(A=(0,0,\dots,0,Z_i,Z_i,\dots Z_i)\) の場合を考えて、いくつかの計算によって示せます。とくに \(Z_i\) は \(1\) 以上であるため、すべての項を \(0\) にすることができません。これにより \(1\) 番目の条件の必要性が導かれます。

\(2\) 番目の条件についてです。 \(S_i=A_1+A_2+\dots +A_{i-1}\) とおきます。

整数列 \(A\) に対し、整数列 \(H=(H_1,H_2,\dots,H_N)\) を漸化式

\[\displaystyle H_i = \max_{\max(i-K+1,1) \leq j \leq \min(i-1,N-K+1)} \lceil \frac{K \times H_j - (S_i - S_j)}{K-(i-j)} \rceil\]

で定めます（ただし、 \(H_1=1\) とする）。定義がわかりにくいですが、 \(H_i \leq i\) なる \(i\) に対し、 \(i\) 項目を含む \(K\) 項に操作を行うと、操作後 \(H_j \leq j\) なる \(j < i\) が存在するようになるような \(A_i\) の最小値をとったような意味の値になります。

\(H_i \leq A_i\) なる \(i\) の最小値を \(i_0\) とし、 \(S_{i+K}-S_i < K \times H_i\) を満たす \(i\) の最小値を \(i_1\) とする。 \(i_0 < i_1\) が成り立つ場合、さきほどのべた \(H\) の性質から、 \(0\) にするのは不可能であることが \(Z_i \leq A_i\) の場合と同様の方法で示せます。また、 \(i_0, i_1\) がいずれも存在しない場合は一度以上操作すると \(H_i \leq A_i\) が成り立ってしまうため、やはりすべての 項を \(0\) にするのは不可能です。

ここで、 \(i\) の昇順にみて \(i_1\) を \(i_0\) より先に発見した場合は以降 \(H_i\) の計算はいらなくなるので、 \(H_i\) を計算する際は \(j \leq i-K\) に対して \(K\times B_{j} \leq S_{j+K}-S_j \) を前提としていいです。また、 \(H_i\) の計算は \(i \leq N-K+1\) でできればいいです。

このとき、実は \(H_i=i\) が成りたつ ことを示します。これが示せれば必要性の証明は完了です。

以下帰納法で示します。 \(i=1\) のときは明らかです。

\(j < i\) に対し \(A_j < H_j=j\) が成り立ち、 \(j \leq i-K\) に対して \(K\times H_{j} \leq S_{j+K}-S_j\) が成り立つものとします。まず \(H_i\) の定義から

\[\displaystyle H_i \geq \lceil \frac{K \times H_{i-1} - A_{i-1}}{K-1} \rceil = i + \lceil \frac{i-K - A_{i-1}}{K-1} \rceil\]

が成り立ち、 \(A_{i-1} < i-1\) より \(H_i \geq i\) が成り立ちます。

あとは \(H_i \leq i\) を示せればよく、これは

\[\displaystyle \lceil \frac{K \times H_j - (S_i - S_j)}{K-(i-j)} \rceil \leq i \iff (S_i-S_j) \geq (i-j)(i-K)\]

が示せればいいです。ここで、 \(A_i\) は単調非減少列であることから \(S_i\) は下に凸であるため、

\[\displaystyle \frac{S_i-S_j}{i-j} \geq \frac{S_i-S_{i-K}}{K} \geq i-K\]

が成り立ちます。以上より示されました。