PythonでK回の部分配列加算操作後に最小値を最大化するアルゴリズム

数値のリスト nums と、2つの整数 size と k が与えられているとします。ここで、「長さ size の連続する部分リストを選び、その範囲内のすべての要素を1ずつ増やす」という操作を考えます。この操作は最大 k 回実行でき、その結果として nums 内で実現可能な最小値の最大値を求めるのがこの問題です。

問題例

たとえば、入力が次のような場合を考えてみましょう。

• nums = [2, 5, 2, 2, 7]
• size = 3
• k = 2

この場合、出力は 3 になります。具体的には、まず [2, 5, 2] の範囲に操作を適用して [3, 6, 3, 2, 7] とし、次に [6, 3, 2] の範囲に操作を適用して [3, 7, 4, 3, 7] を得ます。このとき配列全体の最小値は 3 となり、これが達成できる最大の最小値です。

解法のアプローチ

この問題は「答えに対する二分探索」と「貪欲法による実現可能性判定」を組み合わせることで効率的に解けます。ある目標値 target が「k 回以内の操作で全要素を target 以上にできるか」を判定する関数 possible(target) を用意し、target を二分探索で最大化していきます。

possible() 関数の実装手順

1. 長さ N のゼロ埋めリスト events を用意します。これは区間加算の終了位置を記録するための差分配列です。
2. moves := 0、s := 0 と初期化します。moves は必要な操作回数の累計、s は現在位置に適用済みの加算量です。
3. i を 0 から N-1 まで順に処理します。
   • s := s + events[i] として、この位置で効果が切れる加算分を差し引きます。
   • delta := target - (A[i] + s) を計算し、目標値までの不足分を求めます。
   • delta > 0 の場合は、moves := moves + delta で操作回数を加算し、s := s + delta で現在位置以降への加算を反映します。さらに i + size < N であれば events[i + size] -= delta として、区間の終端で加算を打ち切るよう記録します。
4. 最後に moves <= K であれば true を返します。

メイン処理の手順

1. N := A のサイズとします。
2. left := 0、right := 10^10 と初期化します。
3. left < right の間、以下を繰り返します。
   • mid := (left + right + 1) / 2（切り捨て除算）
   • possible(mid) が真なら left := mid、そうでなければ right := mid - 1
4. ループ終了後、left を返します。これが答えです。

Pythonでの実装例

class Solution:
   def solve(self, A, size, K):
      N = len(A)

      def possible(target):
         events = [0] * N
         moves = s = 0
         for i in range(N):
            s += events[i]
            delta = target - (A[i] + s)
            if delta > 0:
               moves += delta
               s += delta
               if i + size < N:
                  events[i + size] -= delta
         return moves <= K

      left, right = 0, 10 ** 10
      while left < right:
         mid = (left + right + 1) // 2
         if possible(mid):
            left = mid
         else:
            right = mid - 1
      return left

ob = Solution()
nums = [2, 5, 2, 2, 7]
size = 3
k = 2
print(ob.solve(nums, size, k))

入力

[2, 5, 2, 2, 7], 3, 2

出力

3

計算量について

possible() 判定は配列を一度走査するだけなので O(N)、二分探索の反復回数は log(探索範囲の上限) 程度であるため、全体の計算量は O(N log M) となります。素朴なシミュレーションでは非現実的な入力サイズでも、この手法なら高速に答えを求められます。