概要

長さ \(N\) の配列を、長さ \(K\) の連続区間に \(+1\) する操作だけで、どの要素も目標値 \(T_i\) を超えずにちょうど一致させられるかを判定します。

考察

この操作は「区間加算」なので、素朴に「操作するたびに \(K\) 個を更新」していると、操作回数が大きいときに \(O(\text{回数}\times K)\) となり間に合いません（\(T_i\) は最大 \(10^9\)）。

重要な観察は次の2点です。

1. 左から順に見たとき、位置 \(i\) の値を増やせる最後のタイミングが決まっている
   位置 \(i\) を含む長さ \(K\) の区間の開始位置は \(i-K+1 \sim i\) ですが、配列の範囲内で開始できるのは \(1 \sim N-K+1\) です。
   よって、\(i \le N-K+1\) の間は「ここで開始する操作の回数」を決められますが、\(i > N-K+1\)（末尾 \(K-1\) 個）では新しく操作を開始できず、その時点の水分量が目標と一致していないと不可能です。

2. 貪欲に「足りない分だけその場で開始」するのが最適
   左から見て位置 \(i\) の現在水分量を \(cur\) とすると、

   • \(cur > T_i\) なら既に超過しており、減らす手段がないので即 No
   • \(cur < T_i\) なら、位置 \(i\) を増やせるのは「開始位置が \(i\) の操作」も含めてまだ可能なので、不足分 \(T_i-cur\) 回だけ位置 \(i\) から開始すればよい
     こうすると位置 \(i\) は必ずちょうど \(T_i\) になり、以降の決定に影響を残しません。

問題は「現在水分量 \(cur\) を高速に管理すること」ですが、区間加算は差分配列（いもす法）で \(O(1)\) 更新・\(O(1)\) 参照にできます。

アルゴリズム

差分配列 diff を用いて、「これまでに開始した操作が現在位置に与える加算量」を管理します。

• cur を「位置 \(i\) に到達した時点での水分量」とする
• 各 \(i=1..N\) について
  1. cur += diff[i]（過去の操作の影響の開始/終了を反映）
  2. もし \(i \le N-K+1\)（ここから操作開始できる）なら
     
     • need = T[i] - cur
     • need < 0 なら超過なので No
     • need > 0 なら need 回だけ \([i, i+K-1]\) に水やりする
       これは

          - `cur += need`（位置 $i$ には即反映）
          - `diff[i+K] -= need`（$i+K$ 以降では影響が消える）
       

       として表せる
  3. もし \(i > N-K+1\)（もう開始できない）なら
     
     • cur == T[i] でなければ調整不能なので No

最後まで矛盾がなければ Yes です。

（例）\(N=5, K=3, T=[1,2,2,1,0]\) とすると、\(i=1\) で 1 回開始して…というように左から不足分を埋めていき、末尾では一致チェックのみ行います。

計算量

• 時間計算量: \(O(N)\)（各位置を1回ずつ処理）
• 空間計算量: \(O(N)\)（差分配列 diff）

実装のポイント

• last_start = N-K+1 を境に、「操作を開始できる範囲」と「一致チェックしかできない範囲」を分けるのが要点です。

• 差分配列は diff[i+K] -= need のように 終了位置（影響が消える位置） にだけ書き込みます（開始は cur に直接足すため）。

• diff のサイズは i+K が出るので、余裕を持って N+K+5 程度確保しています。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    T = [0] + list(map(int, input().split()))

    diff = [0] * (N + K + 5)
    cur = 0

    last_start = N - K + 1
    for i in range(1, N + 1):
        cur += diff[i]
        if i <= last_start:
            need = T[i] - cur
            if need < 0:
                print("No")
                return
            cur += need
            diff[i + K] -= need
        else:
            if cur != T[i]:
                print("No")
                return

    print("Yes")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。