概要

この問題は、長さ \(N\) の数列 \(A\) を、長さ \(K\) の連続する区間に \(1\) を加算する操作を繰り返すことで、目標の数列 \(B\) に一致させることができるかを判定し、可能な場合はその最小操作回数を求める問題です。

左端から順番に値を確定させていく「貪欲法（Greedy）」と、区間内の加算量を高速に管理する「スライディングウィンドウ」の手法を用いることで、 \(O(N)\) の時間計算量で効率的に解くことができます。

考察

1. 差分への注目

まず、各区画 \(i\) について必要な増加量を \(D_i = B_i - A_i\) とします。 操作によって水分量を「減少」させることはできないため、もし \(D_i < 0\) となる区画が \(1\) つでも存在する場合、目標を達成することは不可能です。したがって、この時点で -1 を出力して終了します。 以降は、すべての \(i\) について \(D_i \ge 0\) であると仮定します。

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

操作は「区画 \(l\) から始まる長さ \(K\) の区間に \(1\) を加算する」というものです。 一番左の区画 \(i = 0\)（0-indexed）に注目してみましょう。区画 \(0\) をカバーできる操作は、区画 \(0\) を左端とする操作（\(l = 0\)）しかありません。 したがって、区画 \(0\) を目標値にするためには、区画 \(0\) を左端とする操作をちょうど \(D_0\) 回行う必要があります。これより多くても少なくてもいけません。

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

次に、区画 \(1\) に注目します。 区画 \(1\) はすでに先ほどの操作によって \(D_0\) だけ水分量が増加しています。したがって、区画 \(1\) を左端とする操作を行うべき回数は、残りの必要量である \(D_1 - D_0\) 回に一意に決定されます。 もし \(D_1 - D_0 < 0\) となってしまった場合、すでに区画 \(1\) の水分量が目標値を超えてしまっていることを意味し、これ以上減らすことはできないため、達成不可能（-1）となります。

このように、左端から順番に「その区画の不足分を補うために、その区画を左端とする操作を何回行うか」を貪欲に決めていくことができます。

3. 操作のシミュレーションの高速化

一般に、区画 \(i\) を処理するとき、それまでに決定した操作によって区画 \(i\) にすでに加算されている値の合計を \(S_i\) とします。 区画 \(i\) を左端とする操作回数を \(x_i\) とすると、以下のように決定できます。

• \(i \le N - K\) のとき（右側に長さ \(K\) の区間を確保できる場合）
  • \(x_i = D_i - S_i\) と決定します。
  • もし \(x_i < 0\) であれば、目標値を超過しているため達成不可能です（-1）。
• \(i > N - K\) のとき（右側に長さ \(K\) の区間を確保できない場合）
  • この区画を左端とする操作は行えません（\(x_i = 0\)）。
  • したがって、すでに加算されている値 \(S_i\) が、目標の差分 \(D_i\) とちょうど一致している必要があります（\(D_i = S_i\)）。一致していなければ達成不可能です（-1）。

ここで、 \(S_i\) を毎回愚直に計算すると、直近 \(K\) 個の \(x\) の和を求める必要があり、全体で \(O(NK)\) の時間がかかってしまいます。 しかし、区画 \(i\) に影響を与える操作は \(x_{i-K+1}\) から \(x_{i-1}\) までの \(K-1\) 個です。 したがって、 \(S_i\) は一歩手前の状態 \(S_{i-1}\) を用いて、 $\(S_i = S_{i-1} + x_{i-1} - x_{i-K}\)\( と表すことができます。 このスライディングウィンドウの考え方を用いることで、各 \)S_i\( を \)O(1)$ で更新しながら進めることができます。

アルゴリズム

1. 各 \(i\) について、必要量 \(D_i = B_i - A_i\) を計算します。 \(D_i < 0\) となるものがあれば -1 を出力します。
2. 各区画を左端とする操作回数を記録する配列 \(x\)（初期値はすべて \(0\)）と、現在の区画にかかっている加算の合計 current_sum を用意します。
3. \(i = 0\) から \(N-1\) まで順に以下を行います。
   • current_sum に \(x[i-1]\) を足し、範囲外となった \(x[i-K]\) を引くことで、現在の区画 \(i\) に適用されている加算の合計を \(O(1)\) で求めます。
   • \(i \le N - K\) の場合：
     • \(x[i] = D_i - \text{current\_sum}\) とします。
     • \(x[i] < 0\) なら -1 を出力して終了します。
     • 合計操作回数 total_ops に \(x[i]\) を加算します。
   • \(i > N - K\) の場合：
     • \(D_i \neq \text{current\_sum}\) なら、目標値に一致させられないため -1 を出力して終了します。
4. すべての区画を矛盾なく処理できれば、 total_ops が求める最小の操作回数となります。

計算量

• 時間計算量: \(O(N)\) 各区画 \(i\) に対する処理は、スライディングウィンドウによる定数回の加減算のみであるため、全体で \(O(N)\) の時間で動作します。
• 空間計算量: \(O(N)\) 入力の配列 \(A, B\)、および差分配列 \(D\)、操作回数配列 \(x\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローの防止: 制約より、操作回数の合計は最大で \(3 \times 10^{14}\) に達することが保証されています。これは通常の 32 ビット整数型（C++の int など）の最大値（約 \(2 \times 10^9\)）を超えるため、操作回数や水分量の計算には必ず 64 ビット整数型（C++の long long）を使用してください。

• インデックスの境界条件: current_sum の更新において、 \(i - 1 < 0\) や \(i - K < 0\) となる場合は、配列の範囲外アクセスを防ぐために条件分岐（if (i >= 1) や if (i >= K)）を適切に行う必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<long long> B(N);
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }

    vector<long long> D(N);
    for (int i = 0; i < N; ++i) {
        D[i] = B[i] - A[i];
        if (D[i] < 0) {
            cout << -1 << "\n";
            return 0;
        }
    }

    vector<long long> x(N, 0);
    long long current_sum = 0;
    long long total_ops = 0;

    for (int i = 0; i < N; ++i) {
        if (i >= 1) {
            current_sum += x[i - 1];
        }
        if (i >= K) {
            current_sum -= x[i - K];
        }

        if (i <= N - K) {
            long long val = D[i] - current_sum;
            if (val < 0) {
                cout << -1 << "\n";
                return 0;
            }
            x[i] = val;
            total_ops += val;
        } else {
            if (D[i] != current_sum) {
                cout << -1 << "\n";
                return 0;
            }
        }
    }

    cout << total_ops << "\n";
    return 0;
}

---

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