概要

長さ \(K\) の連続区間に \(1\) を足す操作を使って、配列 \(A\) をちょうど配列 \(B\) にできるか判定します。
可能なら、そのために必要な操作回数の最小値を求めます。

考察

各区画 \(i\) について、必要な増加量を

\[ D_i = B_i - A_i \]

とします。

操作では水分量を増やすことしかできないので、最終的には各区画 \(i\) にちょうど \(D_i\) だけ加算される必要があります。

ここで重要なのは、左から順に見ていくと、各位置で行うべき操作回数が一意に決まることです。

例えば、区画 \(i\) を見ているとします。
区画 \(i\) に影響を与えられる操作は、開始位置が \(i-K+1\) 以上 \(i\) 以下のものです。

左から順に処理しているとき、すでに開始した操作によって区画 \(i\) に加算されている量を cur とします。

もし区画 \(i\) から新しく操作を開始できるなら、区画 \(i\) の値を目標に合わせるために必要な操作回数は

\[ D_i - cur \]

です。

• \(D_i - cur < 0\) の場合
  すでに目標を超えてしまっているので不可能です。
• \(D_i - cur \geq 0\) の場合
  その回数だけ区画 \(i\) から操作を始めるしかありません。

なぜ「しかない」のかというと、これより右から始まる操作は区画 \(i\) に影響を与えないためです。
つまり、区画 \(i\) をちょうど目標値にする最後のチャンスが、区画 \(i\) から操作を始めるタイミングです。

一方、右端に近い位置では、もう新しく長さ \(K\) の区間を開始できません。
その場合は、すでに行った操作による加算量 cur が \(D_i\) と一致しているかを確認するだけです。

素朴に操作を1回ずつシミュレーションすると、答えが最大で \(3 \times 10^{14}\) 程度になり得るため間に合いません。
また、各操作で長さ \(K\) の区間全体を更新すると \(O(NK)\) になり、これも \(N \leq 3 \times 10^5\) では間に合いません。

そこで、現在位置に影響している操作回数の合計 cur を管理することで、各区画を \(O(1)\) で処理します。

アルゴリズム

\(0\)-indexed で考えます。

操作を開始できる位置は \(0\) から \(N-K\) までなので、その個数を

\[ M = N - K + 1 \]

とします。

used[i] を「位置 \(i\) から開始した操作回数」とします。
また、cur を「現在見ている区画に、すでに開始した操作が与えている加算量」とします。

左から順に \(i = 0, 1, \ldots, N-1\) を処理します。

1. 位置 \(i\) に来たとき、\(K\) 個前に開始した操作はもう影響しないため、必要なら cur から引く

$\( i \geq K \text{ なら } cur \mathrel{-}= used[i-K] \)$

1. 必要な増加量を計算する

$\( d = B_i - A_i \)$

1. まだ位置 \(i\) から操作を開始できる場合、つまり \(i < M\) の場合

現在すでに cur だけ増えているので、追加で必要な操作回数は

$\( add = d - cur \)$

• add < 0 なら不可能
• そうでなければ、位置 \(i\) から add 回操作を開始する

そのため、

   used[i] = add
   cur += add
   ans += add

1. もう操作を開始できない場合、つまり \(i \geq M\) の場合

新しく調整できないので、

$\( cur = d \)$

でなければ不可能です。

最後まで矛盾なく処理できれば、ans が答えです。

例

例えば \(K=3\) で、必要な増加量が

\[ D = [1, 2, 2, 1, 0] \]

だったとします。

左から見ると、

• 位置 \(1\) では cur = 0 なので、\(1\) 回操作開始
• 位置 \(2\) では cur = 1 なので、さらに \(1\) 回操作開始
• 位置 \(3\) では cur = 2 なので、追加操作なし
• 位置 \(4\) 以降は新しく開始できないので、現在の cur が目標と一致するか確認

このように、各位置で開始する操作回数は左から順に一意に決まります。

計算量

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

実装のポイント

• cur は現在位置に影響している操作回数の合計です。

• 位置 \(i\) に来たとき、\(i-K\) から始めた操作は範囲外になるため、cur から引きます。

• 答えは \(32\) bit 整数に収まらない可能性があるため、C++ なら long long を使う必要があります。Python では整数が任意精度なのでそのままで問題ありません。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    M = N - K + 1
    used = [0] * M

    cur = 0
    ans = 0

    for i in range(N):
        if i >= K:
            cur -= used[i - K]

        d = B[i] - A[i]

        if i < M:
            add = d - cur
            if add < 0:
                print(-1)
                return
            used[i] = add
            cur += add
            ans += add
        else:
            if cur != d:
                print(-1)
                return

    print(ans)

if __name__ == "__main__":
    main()

---

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