概要

この問題は、長さ \(N\) の配列 \(A\) を、連続する \(K\) 個の要素に \(1\) を加算する操作を繰り返して配列 \(B\) に一致させることができるかを判定し、可能であれば最小の操作回数を求める問題です。

考察

1. 差分に着目する

まず、各区画 \(i\) について、あとどれだけ水分量を増やす必要があるかを計算します。 \(D_i = B_i - A_i\) とすると、すべての \(D_i\) を \(0\) にすることが目的となります。 操作は「水分量を増やす」ことしかできないため、もし \(D_i < 0\) となる区画が一つでもあれば、その時点で目標達成は不可能（-1）と判断できます。

2. 端から決めていく「貪欲法」

この問題の重要なポイントは、「左端の区画から順に水分量を確定させていく」という考え方です。

区画 \(1\) の水分量を目標値にするためには、区画 \(1\) を左端とする長さ \(K\) の範囲加算を行うしかありません。なぜなら、区画 \(1\) を含む操作の開始位置として、これより左（マイナスのインデックス）は選べないからです。 したがって、区画 \(1\) で不足している量 \(D_1\) だけ、区画 \(1\) を起点とする操作を行うことが確定します。

同様に、区画 \(1\) の調整が終われば、次は区画 \(2\) に着目します。区画 \(2\) ですでに適用されている操作（区画 \(1\) を起点としたもの）を考慮した上で、まだ不足があれば、区画 \(2\) を起点とする操作で補うしかありません。これを \(i = 1, 2, \ldots, N-K+1\) まで繰り返すことで、各地点で必要な操作回数が一意に決まります。

3. 高速化の工夫（いもす法の応用）

素朴に「範囲に \(1\) ずつ加算する」という処理を行うと、各操作に \(O(K)\) かかり、最悪の場合全体の計算量が \(O(NK)\) となってしまいます。\(N, K \leq 2 \times 10^5\) であるため、これでは実行時間制限に間に合いません。

そこで、「現在その地点に影響を与えている操作の合計回数」を効率的に管理する必要があります。 これは「いもす法」や「差分配列」の考え方を用いることで解決できます。 - 変数 current_ops で、現在の区画に及んでいる操作回数の合計を保持します。 - 配列 diff を用意し、diff[i] に「区画 \(i\) で終了する操作の回数」を記録しておきます。 - 次の区画に進む際、current_ops に diff[i] を加算（終了する分を減算）することで、常に \(O(1)\) で現在の状態を把握できます。

アルゴリズム

1. 各区画の不足分 \(D_i = B_i - A_i\) を計算する。\(D_i < 0\) があれば -1 を出力。
2. 「現在適用中の操作回数」を current_ops、「合計操作回数」を total_ops とし、操作の終了タイミングを管理する配列 diff を用意する。
3. \(i = 0\) から \(N-1\) まで順に走査する：
   • current_ops に diff[i] を加える（その地点で終わる操作の影響を反映）。
   • もし \(i \leq N-K\) ならば（まだ操作を開始できる範囲なら）：
     • その区画でさらに必要な回数 needed = D[i] - current_ops を計算。
     • needed < 0 なら、すでに目標を超えているため不可能です（-1）。
     • needed > 0 なら、total_ops と current_ops に needed を加え、diff[i+K] から needed を引く予約をする。
   • もし \(i > N-K\) ならば（もう操作を開始できない範囲なら）：
     • D[i] が current_ops と一致していなければ、調整不可能なので -1。
4. 最後まで矛盾なく走査できれば、total_ops を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 配列の走査は数回であり、各要素に対する処理は定数時間です。
• 空間計算量: \(O(N)\)
  • 不足分を格納する配列 \(D\) や、操作の終了を管理する配列 diff のために \(O(N)\) のメモリを使用します。

実装のポイント

• 操作の終了位置: 区画 \(i\) から始まる長さ \(K\) の操作は、区画 \(i + K - 1\) まで影響を与えます。したがって、影響がなくなるのは区画 \(i + K\) です。diff[i + K] にマイナスの値を記録する際は、インデックスが \(N\) を超えないよう注意が必要です。

• 大きな数値: \(A_i, B_i\) および操作回数は非常に大きな値になる可能性があるため、Pythonのように大きな整数を扱える言語を使用するか、他の言語では 64bit 整数型（long long など）を使用してください。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してメモリ効率よくデータを取得します
    it = iter(input_data)
    
    try:
        N = int(next(it))
        K = int(next(it))
        
        # A_i: 各区画の現在の水分量
        A = [int(next(it)) for _ in range(N)]
        # B_i: 各区画の目標の水分量
        B = [int(next(it)) for _ in range(N)]
    except StopIteration:
        return
    
    # 各区画で不足している水分量 D_i を計算します
    D = [B[i] - A[i] for i in range(N)]
    
    # 水分量を減らす操作はできないため、目標値が現在値より小さい場合は不可能です
    for d in D:
        if d < 0:
            print("-1")
            return
            
    # いもす法（差分配列）の考え方を用いて、範囲加算を効率的に管理します
    # diff[i] は、地点 i で新しく終了する操作による影響（減少分）を記録します
    diff = [0] * (N + 1)
    current_ops = 0 # 現在の区画 i に影響を与えている操作の合計回数
    total_ops = 0   # これまでに行った操作の総回数
    
    # 左から順に、各区画の水分量を目標値に合わせるように貪欲に操作を決定します
    # 操作の開始位置として選べるのは 0 から N-K までです
    for i in range(N - K + 1):
        # 以前の操作のうち、この区画で終了するものの影響を反映します
        current_ops += diff[i]
        
        # 現在の区画 i で不足している水分量
        needed = D[i] - current_ops
        
        if needed < 0:
            # すでに目標値を超えてしまっている場合は不可能です
            print("-1")
            return
        
        if needed > 0:
            # 不足分を補うため、区画 i を開始点とする操作を needed 回行います
            total_ops += needed
            current_ops += needed
            # この操作は区画 i + K - 1 で終わるため、i + K で影響を差し引きます
            if i + K <= N:
                diff[i + K] -= needed
            
    # 操作を開始できない残りの区画（N-K+1 から N-1）について、
    # すでに適用された操作だけで目標値に達しているか確認します
    for i in range(N - K + 1, N):
        current_ops += diff[i]
        if D[i] != current_ops:
            # 目標値に一致しない場合は、これ以上調整できないため不可能です
            print("-1")
            return
            
    # すべての区画が目標値に一致した場合、合計操作回数を出力します
    print(total_ops)

if __name__ == '__main__':
    solve()

---

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