概要

この問題は、長さ \(N\) の配列 \(A\) の連続する長さ \(K\) の区間に \(+1\) する操作を繰り返して、目標の配列 \(B\) に完全に一致させられるかを判定し、可能であればその最小操作回数を求める問題です。

左端から順に貪欲（Greedy）に操作回数を決定していくことで、効率的に解くことができます。

---

考察

1. 差分に着目する

まず、各区画 \(i\)（\(1 \leq i \leq N\)）について、必要な水分増加量 \(D_i = B_i - A_i\) を考えます。 操作によって水分量を減らすことはできないため、もし \(D_i < 0\) となる区画が1つでも存在すれば、目標を達成することは不可能です。この場合は即座に -1 を出力します。

以降は、すべての \(i\) について \(D_i \geq 0\) であるとします。

2. 左端から貪欲に決める

「連続する \(K\) 個の区画に \(+1\) する」という操作において、最も左側にある未解決の区画を基準にするという貪欲法が適用できます。

具体的に、区画 \(1\) を考えてみましょう。 区画 \(1\) をカバーできる操作は、区画 \(1\) を左端とする操作（\(l=1\)）しかありません。したがって、区画 \(1\) の目標を達成するためには、\(l=1\) とする操作をちょうど \(D_1\) 回行う必要があります。

この操作を行うと、区画 \(1\) から区画 \(K\) までのすべての水分量が \(D_1\) だけ増加します。

次に、区画 \(2\) を考えます。 区画 \(2\) はすでに \(l=1\) の操作によって \(D_1\) だけ増加しています。したがって、区画 \(2\) を左端とする操作（\(l=2\)）を行うべき回数 \(x_2\) は、不足分である \(D_2 - D_1\) 回となります。 もし \(D_2 - D_1 < 0\) となってしまった場合は、すでに目標値を超えてしまっているため、達成不可能（-1）と判定できます。

3. 一般化と高速化

これを一般化します。区画 \(i\) を左端とする操作回数を \(x_i\) とします。 区画 \(i\) に影響を与えているこれまでの操作の合計回数を \(S\) とすると、区画 \(i\) で新たに行うべき操作回数 \(x_i\) は次のように決まります。

• \(i \leq N - K + 1\) のとき（操作を開始できる場合）
  • \(x_i = D_i - S\)
  • もし \(x_i < 0\) なら、目標を超過しているため達成不可能（-1）。
  • そうでなければ、新たに \(x_i\) 回の操作を行い、合計回数 \(S\) に \(x_i\) を加算します。
• \(i > N - K + 1\) のとき（新しく操作を開始できない場合）
  • この区画では新しく操作を始められないため、現在の累積増加量 \(S\) がちょうど \(D_i\) と一致している必要があります。
  • \(D_i - S \neq 0\) であれば、達成不可能（-1）。

ここで、素直に毎回 \(K\) 個の区画に値を足し合わせるシミュレーションを行うと、1回の操作に \(O(K)\) かかり、全体で \(O(NK)\) の計算量になります。\(N \leq 3 \times 10^5\) であるため、これでは実行時間制限（TLE）になってしまいます。

そこで、スライディングウィンドウの要領で \(S\) を管理します。 区画 \(i\) に進むとき、影響範囲から外れた操作（すなわち区画 \(i-K\) を左端とする操作 \(x_{i-K}\)）の分だけ \(S\) から差し引く（\(S \leftarrow S - x_{i-K}\)）ことで、現在の影響合計 \(S\) を \(O(1)\) で更新していくことができます。

---

アルゴリズム

1. 各区画 \(i\) について、必要な増加量 \(D_i = B_i - A_i\) を計算します。この時点で \(D_i < 0\) があれば -1 を出力して終了します。
2. 操作回数を記録する配列 \(x\)（サイズ \(N+1\)、初期値 \(0\)）、現在の累積操作回数 \(S = 0\)、答えの合計 ans = 0 を用意します。
3. \(i = 1\) から \(N\) まで順にループを回します（1-indexed で考えます）。
   • ステップ A: \(i - K \geq 1\) であれば、影響範囲から外れた操作回数を引きます： \(S \leftarrow S - x_{i-K}\)
   • ステップ B:
     • \(i \leq N - K + 1\) の場合：

          * 必要な追加操作回数 $x_i = D_{i} - S$ を計算します。
          * $x_i < 0$ なら、超過しているため `-1` を出力して終了します。
          * $S \leftarrow S + x_i$ と更新し、`ans` に $x_i$ を加算します。
       

     • \(i > N - K + 1\) の場合：

          * 新たな操作は行えないため、現在の $S$ が $D_i$ と等しいか確認します。
          * $D_i - S \neq 0$ なら、目標と一致しないため `-1` を出力して終了します。
       

4. ループが矛盾なく終了すれば、ans を出力します。

---

計算量

• 時間計算量: \(O(N)\) 各区画 \(i\) に対して、値の比較と加減算を定数回行うだけなので、全体の計算量は \(O(N)\) となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(N)\) 入力配列や差分配列 \(D\)、操作回数配列 \(x\) を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• オーバーフローへの注意: 必要な最大操作回数は最大で \(3 \times 10^{14}\) に達することが保証されています。Pythonでは自動的に多倍長整数が扱われるため問題ありませんが、C++やJavaなどの他言語で実装する場合は、操作回数やその合計を保持する変数に 64 ビット整数型（C++の long long など）を使用する必要があります。

• インデックスの対応: コード中では区画のインデックスが 0-indexed（\(0\) から \(N-1\)）であるのに対し、操作の管理用の配列 \(x\) は 1-indexed（\(1\) から \(N\)）で扱うと、範囲外参照を防ぎやすく実装がスッキリします。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2 : 2 + N]]
    B = [int(x) for x in data[2 + N : 2 + 2 * N]]

    D = [0] * N
    for i in range(N):
        D[i] = B[i] - A[i]
        if D[i] < 0:
            print(-1)
            return

    x = [0] * (N + 1)
    S = 0
    ans = 0

    limit = N - K + 1
    for i in range(1, N + 1):
        if i - K >= 1:
            S -= x[i - K]

        if i <= limit:
            xi = D[i - 1] - S
            if xi < 0:
                print(-1)
                return
            x[i] = xi
            S += xi
            ans += xi
        else:
            if D[i - 1] - S != 0:
                print(-1)
                return

    print(ans)


if __name__ == "__main__":
    solve()

---

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