D - Range Add Query Editorial by Mitsubachi

nok0 さんの解説の補足

実は、この条件が $X$ が良い数列であることの十分条件であることも言えます。証明は簡単なので読者への課題とします。
これの証明をします。 $X$ の長さを $n$ とします。添え字は 0-indexed とします。
すなわち $X = \left( X_0,X_1, \cdots , X_{n-1} \right)$ と扱い、操作で選べる $i$ の範囲は $0 \leq i \leq n-K$ とします。

\([\rm{I}]\) \(n=K\) のとき

\(0 \leq i < K\) において \(S_i = X_i\) です。よって \(X\) の要素は全て等しいです。

よって \(i=0,c=-X_0\) を選んで操作することで \(X\) の要素は全て \(X_i + \left( -X_0 \right) = 0\) となります。よって十分性が成り立ちます。

\([\rm{I\hspace{-.01em}I}]\) \(n=m\) で十分性が成り立つとき

\(n=m+1\) の場合を考えます。 \(i=1,c=-X_m\) を選んで操作することで \(X = \left( X_0,X_1-X_m, \cdots , X_{m-1}-X_m,0 \right)\) となります。末尾の \(0\)\(X\) から削除しても 良い数列 であればよいです。

このときの \(S_0,S_1, \cdots ,S_{K-1}\) は全て最初の状態から \(X_m\) だけ引かれているので \(S_i\) は全て等しいです。 \(n=m\) で十分性が成り立つので \(X\) の先頭 \(m\) 項をここから全て \(0\) にできます。

以上より \(n=m+1\) でも十分性が成り立ちます。

以上より数学的帰納法で示されました。

posted:
last update: