概要

この問題は、長さ \(N\) の数列 \(T\) が与えられたとき、長さ \(K\) の区間に \(1\) を加算する操作を繰り返して、初期状態（すべて \(0\)）から \(T\) を完全に再現できるかを判定する問題です。

考察

一見すると、どの区間に何回水をまくべきか選ぶのが難しそうに見えますが、左端の区画から順番に見ていくことで、各位置で開始すべきスプリンクラーの回数が一意に決まることに注目しましょう。

重要な観察

\(i\) 番目の区画の水分量 \(T_i\) は、その区画をカバーするスプリンクラーの操作回数の合計です。 ここで、\(i\) 番目の区画から開始するスプリンクラーの回数を \(x_i\) とします。スプリンクラーは連続する \(K\) 区画に水をまくため、区画 \(i\) に影響を与えるのは \(x_{i-K+1}, x_{i-K+2}, \ldots, x_i\) のいずれかです。

1. 区画 1 の場合: 区画 1 をカバーできるのは、インデックス 1 から始まるスプリンクラーのみです。したがって、\(x_1 = T_1\) と決まります。
2. 区画 \(j \le K\) の場合: 区画 \(j\) をカバーするのは \(x_1, x_2, \ldots, x_j\) です。 \(T_j = x_1 + x_2 + \dots + x_j\) \(T_{j-1} = x_1 + x_2 + \dots + x_{j-1}\) この差をとると、\(x_j = T_j - T_{j-1}\) となります。
3. 区画 \(j > K\) の場合: 区画 \(j\) をカバーするのは \(x_{j-K+1}, \ldots, x_j\) です。 \(T_j = x_{j-K+1} + \dots + x_j\) \(T_{j-1} = x_{j-K} + \dots + x_{j-1}\) この差をとると、\(T_j - T_{j-1} = x_j - x_{j-K}\) となり、変形すると \(x_j = T_j - T_{j-1} + x_{j-K}\) が得られます。

判定のポイント

• 非負整数であること: スプリンクラーの回数 \(x_i\) は \(0\) 以上の整数でなければなりません。計算の途中で \(x_i < 0\) となった場合は、その時点で No と判定できます。
• 範囲外の整合性: スプリンクラーを開始できるのは \(N-K+1\) 番目の区画までです。それ以降（\(j > N-K+1\)）の区画については、新しくスプリンクラーを開始できないため、既存の \(x\) の値だけで目標水分量 \(T_j\) を満たしているかを確認する必要があります。

アルゴリズム

1. \(x\) を長さ \(N-K+1\) の配列（初期値 \(0\)）として用意します。
2. \(j = 1\) から \(N\) まで順番にループを回します。
3. \(j \le N-K+1\) のとき（新しいスプリンクラーを開始できる場合）:
   • \(j \le K\) なら \(x_j = T_j - T_{j-1}\)
   • \(j > K\) なら \(x_j = T_j - T_{j-1} + x_{j-K}\)
   • もし \(x_j < 0\) なら No を出力して終了。
4. \(j > N-K+1\) のとき（新しいスプリンクラーを開始できない場合）:
   • \(j \le K\) なら \(T_j = T_{j-1}\) であるか確認。
   • \(j > K\) なら \(T_j = T_{j-1} - x_{j-K}\) であるか確認。
   • 矛盾があれば No を出力して終了。
5. 最後まで矛盾なく計算できれば Yes を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 数列を \(1\) 回走査するだけなので、非常に高速です。
• 空間計算量: \(O(N)\)
  • 入力配列 \(T\) と、操作回数を記録する配列 \(x\) のメモリが必要です。

実装のポイント

• インデックスの扱い: 数式では \(1\)-indexed で考えましたが、プログラム上では \(0\)-indexed になるため、T[j-1] や x[j-K-1] のようにインデックスがずれる点に注意しましょう。

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Python の場合は sys.stdin.read().split() を使うなど、入力を一括で読み込む工夫をすると安全です。

  ソースコード

import sys

def solve():
    # Read all input at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    # T represents the target moisture levels for each of the N sections
    T = list(map(int, input_data[2:]))
    
    # x[i] will store the number of times a sprinkler is used starting at index i.
    # There are N-K+1 possible starting positions for the sprinkler.
    x = [0] * (N - K + 1)
    
    for j in range(1, N + 1):
        # Target moisture for the current section (1-indexed j)
        t_curr = T[j-1]
        t_prev = T[j-2] if j > 1 else 0
        
        if j <= N - K + 1:
            # For sections where a new sprinkler can start
            if j <= K:
                # When j <= K, the moisture at j is the sum of all sprinklers starting at 1...j
                # T_j = x_1 + ... + x_j
                # T_{j-1} = x_1 + ... + x_{j-1}
                # Therefore, x_j = T_j - T_{j-1}
                x[j-1] = t_curr - t_prev
            else:
                # When j > K, the moisture at j is the sum of sprinklers starting at j-K+1...j
                # T_j = x_{j-K+1} + ... + x_j
                # T_{j-1} = x_{j-K} + ... + x_{j-1}
                # T_j - T_{j-1} = x_j - x_{j-K}
                # Therefore, x_j = T_j - T_{j-1} + x_{j-K}
                x[j-1] = t_curr - t_prev + x[j-K-1]
            
            # The number of times a sprinkler is used must be a non-negative integer.
            # If x[j-1] is negative, it's impossible to reach the target exactly.
            if x[j-1] < 0:
                print("No")
                return
        else:
            # For sections where no new sprinkler can start (j > N-K+1)
            # We check if the moisture level matches the target.
            if j <= K:
                # If j <= K and j > N-K+1, the moisture is the sum of all available sprinklers.
                # The moisture level should not change from the previous section.
                if t_curr != t_prev:
                    print("No")
                    return
            else:
                # If j > K and j > N-K+1, the moisture at j is the sum of x_{j-K+1}...x_{N-K+1}.
                # The change in moisture from the previous section must be -x_{j-K}.
                if t_curr != t_prev - x[j-K-1]:
                    print("No")
                    return
                    
    # If all sections match their target moisture levels exactly, output Yes.
    print("Yes")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。