概要

連続する \(K\) 区画の水分量を \(1\) ずつ増やす操作を繰り返して、各区画の水分量を現在値 \(A_i\) から目標値 \(B_i\) にちょうど一致させられるか判定し、可能なら最小操作回数を求める問題です。

考察

操作の定式化

各操作の開始位置 \(l\)（\(0\)-indexed で \(0 \leq l \leq M-1\)、ただし \(M = N - K + 1\)）を選ぶ回数を \(x_l\) とします。すると、区画 \(i\) が受ける水分量の増加は、区画 \(i\) をカバーするすべての操作の合計です：

\[A_i + \sum_{\max(0,\, i-K+1) \leq l \leq \min(i,\, M-1)} x_l = B_i\]

つまり各 \(x_l \geq 0\) のもとでこの等式を全区画で満たす必要があります。

貪欲に一意に決まる

左から順に区画を見ていくと、区画 \(i\)（\(i < M\)）について： - すでに決定した \(x_0, x_1, \ldots, x_{i-1}\) のうち区画 \(i\) をカバーするものの合計を current_sum とする - 等式を満たすには \(x_i = (B_i - A_i) - \text{current\_sum}\) と一意に決まる - \(x_i < 0\) になれば不可能（水分量は減らせない）

区画 \(i \geq M\) については新たな操作を開始できないため、既存の操作だけで等式が成り立つか検証するだけです。

なぜこれが最小か

各 \(x_l\) は等式制約から一意に定まるため、解が存在すれば操作回数 \(\sum x_l\) も一意です。よって存在する解がそのまま最小解になります。

アルゴリズム

1. \(M = N - K + 1\) として配列 \(x\) を用意する
2. current_sum（現在の区画をカバーしている操作の合計）を管理しながら左から右へ走査する
3. 各区画 \(i\) について：
   • \(i \geq K\) なら、\(x_{i-K}\) はもう区画 \(i\) をカバーしないので current_sum から引く（スライディングウィンドウ）
   • \(i < M\) なら、\(x_i = B_i - A_i - \text{current\_sum}\) を計算。負なら -1 を出力して終了。そうでなければ current_sum に加算し、total にも加算
   • \(i \geq M\) なら、current_sum \(= B_i - A_i\) でなければ -1 を出力
4. 全区画を問題なく処理できれば total を出力

具体例

\(N=5, K=3, A=[1,2,3,4,5], B=[3,5,6,6,5]\) の場合： - 必要増加量 \(D = B - A = [2, 3, 3, 2, 0]\) - \(i=0\): \(x_0 = 2 - 0 = 2\), current_sum\(=2\) - \(i=1\): \(x_1 = 3 - 2 = 1\), current_sum\(=3\) - \(i=2\): \(x_2 = 3 - 3 = 0\), current_sum\(=3\) - \(i=3\)（検証）: current_sum から \(x_0=2\) を引いて \(1\)、\(D_3=2\) と不一致 → -1

計算量

• 時間計算量: \(O(N)\)（配列を一回走査するだけ）
• 空間計算量: \(O(N)\)（配列 \(x\) の格納）

実装のポイント

• スライディングウィンドウ: current_sum から \(x_{i-K}\) を引くことで、区画 \(i\) をカバーしている操作の合計を \(O(1)\) で更新できる

• オーバーフロー注意: 最小操作回数が \(3 \times 10^{14}\) まであり得るため、64ビット整数が必要（Python では自動で多倍長整数なので問題なし）

• 前半と後半の場合分け: \(i < M\) では \(x_i\) を決定し、\(i \geq M\) では検証のみ行う点に注意

  ソースコード

import sys
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    M = N - K + 1
    x = [0] * M
    
    current_sum = 0
    total = 0
    
    for i in range(N):
        if i >= K:
            current_sum -= x[i - K]
        if i < M:
            xi = B[i] - A[i] - current_sum
            if xi < 0:
                print(-1)
                return
            x[i] = xi
            current_sum += xi
            total += xi
        else:
            if current_sum != B[i] - A[i]:
                print(-1)
                return
    
    print(total)

solve()

---

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