概要

長さ \(K\) の連続区間に +1 する操作を繰り返し、配列 \(A\) をちょうど配列 \(B\) にできるか判定し、可能なら最小操作回数を求める問題です。実は操作回数の割り当ては一意に定まるため、それが妥当かどうかを検証するだけで解けます。

考察

差分配列の導入

まず \(D_i = B_i - A_i\)（各区画に必要な増加量）を計算します。操作は水分量を増やすことしかできないので、\(D_i < 0\) となる区画が1つでもあれば即座に不可能です。

操作回数の一意性

\(M = N - K + 1\) とし、位置 \(l\) を始点とする操作の回数を \(x_l\)（\(l = 1, \ldots, M\)）とします。\(P_i = x_1 + x_2 + \cdots + x_i\)（\(x\) の累積和）と定義すると、区画 \(i\) に対する制約は以下のようになります：

• \(1 \leq i \leq K\)（かつ \(i \leq M\)）の場合: 区画 \(i\) に影響する操作は \(l = 1, \ldots, i\) なので \(P_i = D_i\)
• \(K < i \leq M\) の場合: 影響する操作は \(l = i-K+1, \ldots, i\) なので \(P_i - P_{i-K} = D_i\)、つまり \(P_i = D_i + P_{i-K}\)
• \(M < i \leq N\) の場合: 影響する操作は \(l = i-K+1, \ldots, M\) なので \(P_M - P_{i-K} = D_i\)

最初の2つの式から、\(P_1, P_2, \ldots, P_M\) が一意に決まります。つまり、解が存在するなら操作回数の割り当ては1通りしかなく、その合計 \(P_M\) が答えです。

検証すべき条件

1. すべての \(D_i \geq 0\)
2. すべての \(x_l = P_l - P_{l-1} \geq 0\)（操作回数は非負）
3. 位置 \(M+1\) 以降の区画について \(P_M - P_{i-K} = D_i\) が成り立つ

アルゴリズム

1. \(D_i = B_i - A_i\) を計算。\(D_i < 0\) があれば -1。
2. 累積和 \(P\) を構築：
   • \(i \leq K\) なら \(P_i = D_i\)
   • \(i > K\) なら \(P_i = D_i + P_{i-K}\)
3. 非負性チェック：\(P_i - P_{i-1} \geq 0\)（\(P_0 = 0\)）を全 \(i\) で確認。
4. 整合性チェック：\(i = M+1, \ldots, N\) に対して \(P_M - P_{\max(0, i-K)} = D_i\) を確認。
5. すべて通れば \(P_M\) を出力。

具体例

\(N = 5, K = 3, M = 3\)、\(D = [2, 3, 4, 2, 1]\) の場合：

• \(P_1 = 2, P_2 = 3, P_3 = 4\)
• \(x_1 = 2, x_2 = 1, x_3 = 1\)（すべて非負 ✓）
• 区画4: \(P_3 - P_1 = 4 - 2 = 2 = D_4\) ✓
• 区画5: \(P_3 - P_2 = 4 - 3 = 1 = D_5\) ✓
• 答え: \(P_3 = 4\)

計算量

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

実装のポイント

• \(P_M\)（答え）が \(3 \times 10^{14}\) に達し得るため、long long を使用する。

• 累積和の添字管理で \(P_0 = 0\) を初期値として設定する。

• \(i - K \leq 0\) のケースでは \(P_0 = 0\) を使う（max(0, i-K) で処理）。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    
    vector<long long> A(N+1), B(N+1), D(N+1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];
    
    for (int i = 1; i <= N; i++) {
        D[i] = B[i] - A[i];
        if (D[i] < 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    int M = N - K + 1;
    vector<long long> S(M+1, 0);
    
    for (int i = 1; i <= M; i++) {
        if (i <= K) {
            S[i] = D[i];
        } else {
            S[i] = D[i] + S[i-K];
        }
    }
    
    for (int i = 1; i <= M; i++) {
        if (S[i] - S[i-1] < 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    for (int i = M+1; i <= N; i++) {
        int lower_minus_1 = max(0, i - K);
        long long expected = S[M] - S[lower_minus_1];
        if (expected != D[i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    cout << S[M] << endl;
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。