概要

各区画について、現在値 \(A_i\) から目標値 \(B_i\) まで増やす必要がある量を考えます。
長さ \(K\) の区間加算操作だけで、すべての区画をちょうど目標値にできるか判定し、できるなら最小操作回数を求めます。

考察

区画 \(i\) に必要な増加量を

\[ D_i = B_i - A_i \]

とします。

操作は水分量を増やすことしかできないため、最終的に各区画にはちょうど \(D_i\) 回分の加算が必要です。

重要な気づきは、左から順に見ていくと、その位置で新しく始める操作回数は一意に決まるということです。

例えば、区画 \(i\) を見ているとします。

• すでに左側で始めた操作によって、区画 \(i\) には cur 回分の加算が入っている
• 区画 \(i\) を目標にするには、合計で \(D_i\) 回加算されている必要がある
• これから右側で始める操作は、区画 \(i\) には影響しない

したがって、もし区画 \(i\) で操作を開始できるなら、区画 \(i\) から始める操作回数は

\[ D_i - cur \]

でなければなりません。

この値が負の場合、すでに加算しすぎているので不可能です。

また、操作を開始できる位置は \(1\) から \(N-K+1\) までです。
そのため、\(i > N-K+1\) の位置では新しく操作を始めることができません。
この場合は、すでに入っている加算量 cur が \(D_i\) と一致していなければ不可能です。

素朴な方法では間に合わない理由

区画 \(i\) で操作を need 回行うとして、実際に区間 \([i, i+K-1]\) の各要素を毎回更新すると、最悪で

\[ O(NK) \]

または操作回数が大きい場合はさらに膨大な計算量になってしまいます。

\(N\) は最大 \(3 \times 10^5\) なので、これは間に合いません。

そこで、区間加算を効率よく管理するために、いもす法の考え方を使います。

アルゴリズム

左から順に区画を見ていきます。

変数を次のように持ちます。

• cur: 現在の区画に、これまでの操作によって加算されている量
• diff: いもす法用の配列
• ans: 操作回数の合計
• lastStart = N - K + 1: 操作を開始できる最後の位置

区画 \(i\) に来たら、まず

cur += diff[i];

として、区画 \(i\) に入る加算量を反映します。

次に、区画 \(i\) に必要な増加量を

\[ target = B_i - A_i \]

とします。

\(i \leq lastStart\) の場合

この位置から操作を開始できます。

このとき、区画 \(i\) をちょうど目標値にするには

\[ need = target - cur \]

回、区画 \(i\) から操作を始める必要があります。

• need < 0 なら、すでに加算しすぎなので不可能
• そうでなければ、need 回操作する

操作を need 回始めると、区間 \([i, i+K-1]\) に need が加算されます。

そのため、

cur += need;
diff[i + K] -= need;

として、区間の終わりの次の位置で効果が切れるようにします。

そして操作回数に加えます。

ans += need;

\(i > lastStart\) の場合

この位置からはもう操作を開始できません。

したがって、すでに加算されている量 cur がちょうど target と等しい必要があります。

if (cur != target) {
    不可能
}

もしすべての区画を確認して問題なければ、ans が答えです。

具体例

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

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

だとします。

• 区画 \(1\) ではまだ加算量は \(0\)
  必要量は \(1\) なので、位置 \(1\) から \(1\) 回操作する
• 区画 \(2\) ではすでに \(1\) 加算されている
  必要量は \(2\) なので、位置 \(2\) から \(1\) 回操作する
• 区画 \(3\) ではすでに \(2\) 加算されている
  必要量も \(2\) なので、新たな操作は不要
• 区画 \(4,5\) ではもう新しく操作を開始できないので、現在の加算量が必要量と一致するかだけ確認する

このように、左から順に見ることで各位置で行うべき操作回数が決まります。

計算量

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

実装のポイント

• 操作回数の合計は大きくなる可能性があるため、long long を使います。
• diff[i + K] -= need により、区間加算の効果が \(i+K\) 以降で消えるようにします。
• 配列は \(1\)-indexed にすると、区間 \([i, i+K-1]\) を扱いやすくなります。
• 操作を開始できる最後の位置は

\[ N - K + 1 \]

です。これより右では新しく操作を始められないことに注意します。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<long long> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];

    vector<long long> diff(N + 2, 0);

    long long cur = 0;
    long long ans = 0;
    int lastStart = N - K + 1;

    for (int i = 1; i <= N; i++) {
        cur += diff[i];

        long long target = B[i] - A[i];

        if (i <= lastStart) {
            long long need = target - cur;
            if (need < 0) {
                cout << -1 << '\n';
                return 0;
            }

            ans += need;
            cur += need;

            if (i + K <= N + 1) {
                diff[i + K] -= need;
            }
        } else {
            if (cur != target) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

---

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