概要

連続する \(K\) 区画に同時に水をまけるスプリンクラーを使って、各區画の水分量をちょうど目標値にできるか判定する問題です。

考察

この問題では、スプリンクラーを何回使えば目標を達成できるかという直接的なシミュレーションではなく、「どのように水をまけば各区画の水分量が目標値と一致するか」という視点が必要です。

ここで重要なのは、スプリンクラーの操作は連続する \(K\) 区画に同じ量の水分を加えるということです。つまり、各区画の最終的な水分量を達成するために必要な「操作回数の分布」を考えると効率的です。

差分の考えかた

例えば、目標水分量の配列 \(T = [2, 3, 3, 2]\) のとき、スプリンクラーをある回数使った結果、各区画にどれだけの操作が「初めて適用されたか」を逆算することで判断できます。

しかし、愚直にシミュレーションすると、各区画ごとに操作回数を記録して加算していくため、最大で \(10^9\) 回程度の操作が必要になり、時間的に無理があります（TLE）。

そこで、累積和の逆操作、つまり差分を用いるのが定石です。

差分配列とは？

配列 \(T\) の隣接要素の差を取った配列： $\( \text{diff}[i] = \begin{cases} T[0] & (i = 0) \\ T[i] - T[i-1] & (i > 0) \end{cases} \)$

この差分配列を使うことで、操作の影響範囲（連続 \(K\) 区画）を効率的に表現できます。

なぜなら、スプリンクラーを区間 \([l, l+K-1]\) に使うことは、差分配列上で以下のように変化させます： - \(\text{diff}[l]\) に \(+1\) - \(\text{diff}[l+K]\) に \(-1\)

つまり、区間加算を2点更新で表現できるのです。

したがって、目標となる水分量に対応する差分配列から、それが非負の操作回数によって構成可能かを判定すればよいのです。

具体的には以下の条件をチェックします：

1. 最初の \(K-1\) 個の差分が非負であること（左端から \(K\) 区画未満の区間に操作を始められないため）
2. \(K\) 番目以降の差分について、\(\text{diff}[i] = \text{diff}[i-K] + (T[i] - T[i-1])\) が常に非負であること（操作が前の区間から伝搬してくるため）
3. 最後の \(K-1\) 個の差分がすべてゼロであること（それより右に操作を開始できないため）

アルゴリズム

1. 目標水分量配列 \(T\) から差分配列 \(\text{diff}\) を作成する。
2. \(\text{diff}\) の最初の \(K-1\) 項がすべて非負であることを確認。
3. \(K\) 番目以降については、\(\text{diff}[i] = \text{diff}[i] + \text{diff}[i - K]\) として操作の伝搬を反映しながら非負かチェック。
4. 最後 \(K-1\) 項がすべてゼロであることを確認。
5. すべてOKなら Yes、そうでなければ No を出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 差分配列のサイズは \(N+1\) にしておくと、\(\text{diff}[i+K]\) への減算処理が安全に行える。
• 最後の \(K-1\) 項のチェックを忘れずに。
• Python では高速な入力処理（sys.stdin.readなど）を使用することを推奨。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    T = list(map(int, data[2:]))

    # 差分の配列を作成
    diff = [0] * (N + 1)
    diff[0] = T[0]
    for i in range(1, N):
        diff[i] = T[i] - T[i-1]
    
    # 最初のK-1個の差分が非負であることを確認
    for i in range(K-1):
        if diff[i] < 0:
            print("No")
            return
    
    # K番目以降の差分をチェック
    for i in range(K, N):
        diff[i] += diff[i - K]
        if diff[i] < 0:
            print("No")
            return
    
    # 最後のK-1個の差分がゼロであることを確認
    for i in range(N - K + 1, N):
        if diff[i] != 0:
            print("No")
            return

    print("Yes")

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。