Pythonで解く「不機嫌な書店のオーナー」問題 ― スライディングウィンドウによる最適化手法

問題の概要

ある書店のオーナーが、customers リストの要素数に等しい分数だけ店を開けているとします。毎分 customers[i] 人の客が入店し、その分が終わると全員が退店します。オーナーには機嫌の良い時間帯と悪い時間帯があり、i 分目に不機嫌であれば grumpy[i] = 1、そうでなければ grumpy[i] = 0 と表されます。

オーナーが不機嫌な分に入店した客は不満を抱き、機嫌が良い分に入店した客は満足します。ここで、オーナーは「X 分連続で不機嫌にならないようにするテクニック」を知っていますが、このテクニックは一度しか使えません。この条件のもとで、一日を通じて満足できる客の数の最大値を求めるのが本問題です。

たとえば、customers = [1,0,1,2,1,1,7,5]、grumpy = [0,1,0,1,0,1,0,1]、X = 3 の場合、出力は 16 になります。これは、オーナーが最後の 3 分間だけ機嫌を良くすることで、それ以外の時間帯の満足客 1 + 1 + 1 + 1 に加え、不機嫌だった時間帯の客 7 + 5 も満足させられるためです。合計は 1 + 1 + 1 + 1 + 7 + 5 = 16 となります。

解法のアプローチ：スライディングウィンドウ

この問題は、長さ X の「窓」を配列上でスライドさせながら、窓の中で不機嫌な時間帯に来店した客の総数を追跡するスライディングウィンドウ（尺取り法）で効率的に解けます。窓ごとの不満客の合計を記録しておき、その最大となる区間を見つけたら、その区間の grumpy の値をすべて 0 に変更します。最後に、grumpy が 0 の時間帯の客数をすべて合計すれば答えが得られます。

アルゴリズムの手順

• i := 0、j := 0、sums := 空リスト、temp := 0 で初期化する

• j − i + 1 < X の間、次を繰り返す：

  • grumpy[j] が 1 なら temp := temp + customers[j]

  • j を 1 増やす

• [temp, i, j] を sums に挿入する

• i と j をそれぞれ 1 増やす

• j < customers の長さ の間、次を繰り返す：

  • grumpy[i − 1] が 1 なら temp := temp − customers[i − 1]（窓から外れる分を除く）

  • grumpy[j] が 1 なら temp := temp + customers[j]（窓に入る分を加える）

  • [temp, i, j] を sums に挿入する

  • i と j をそれぞれ 1 増やす

• sums を内側リストの先頭要素（不満客の合計）でソートする

• index1 := sums の最後のリストの第 2 要素、index2 := 同じく第 3 要素とする

• index1 から index2 までの範囲で grumpy[i] := 0 とする

• ans := 0 と初期化する

• i を 0 から customers の長さまで動かしながら、grumpy[i] が 0 なら ans := ans + customers[i]

• ans を返す

Python 実装例

以下のコードで実際の動作を確認できます。

class Solution(object):
   def maxSatisfied(self, customers, grumpy, X):
      i = 0
      j = 0
      sums = []
      temp = 0
      while j-i+1<X:
         if grumpy[j]:
            temp+=customers[j]
         j+=1
      sums.append([temp,i,j])
      i+=1
      j+=1
      while j<len(customers):
         if grumpy[i-1]:
            temp-=customers[i-1]
         if grumpy[j]:
            temp+=customers[j]
         sums.append([temp,i,j])
         i+=1
         j+=1
      sums =sorted(sums,key = lambda v : v[0])
      index1 = sums[-1][1]
      index2 = sums[-1][2]
      for i in range(index1,index2+1):
         grumpy[i] = 0
      ans = 0
      for i in range(len(customers)):
         if not grumpy[i]:
            ans+=customers[i]
      return ans
ob = Solution()
print(ob.maxSatisfied([1,0,1,2,1,1,7,5],[0,1,0,1,0,1,0,1],3))

入力

[1,0,1,2,1,1,7,5]
[0,1,0,1,0,1,0,1]
3

出力

16

計算量と補足

この実装では、すべての窓の情報を sums リストに保持しソートしているため、時間計算量は O(n log n)、空間計算量は O(n) となります。実は、窓ごとの最大値を走査しながら記録すればソートは不要で、O(n) 時間・O(1) 追加空間にまで削減できます。また、最終的な答えは「grumpy が最初から 0 の分の客数の合計 ＋ テクニック適用区間で救える不満客の最大数」という式で直接求められる点も覚えておくと便利です。