Pythonで解くダイエットプランのパフォーマンス問題 ― スライディングウィンドウによる効率的な実装

ダイエット中の人が i 日目に摂取したカロリーを calories[i] と表します。整数 k が与えられたとき、連続する k 日間の各区間（calories[i], calories[i+1], ..., calories[i+k-1]、ただし 0 <= i <= n-k）について、その期間の合計カロリー T を計算し、次のルールに従ってポイントを評価します。

• T が下限（lower）より小さい場合：ダイエットの成果が不良のため、1ポイント減点
• T が上限（upper）より大きい場合：ダイエットの成果が良好なため、1ポイント加点
• それ以外の場合：正常な範囲内のため、ポイント変動なし

ダイエット開始時のポイントは0です。このとき、最終的な合計ポイントを求めるのが本問題の目的です。

具体例

配列が [6,5,0,0]、k = 2、lower = 1、upper = 5 の場合を考えてみましょう。

• C[0] + C[1] = 11 > upper なので、1ポイント加算
• lower <= C[1] + C[2] = 5 <= upper なので、変化なし
• C[2] + C[3] = 0 < lower なので、1ポイント減点

加算と減点が相殺されるため、出力は 0 となります。

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

すべての区間に対して毎回合計を再計算すると非効率ですが、スライディングウィンドウ（尺取り法）を使えば、直前の区間の合計を再利用できるため、全体を線形時間 O(n) で処理できます。手順は以下の通りです。

• temp = 0 で初期化する
• i を 0 から k-1 までループし、temp += C[i] で最初のウィンドウの合計を求める
• right = k - 1、left = 0、points = 0 で初期化する
• right が C の長さ未満である間、以下を繰り返す：
  • temp < lower なら points を1減らし、temp > upper なら1増やす
  • temp -= C[left] で左端の要素をウィンドウから除外する
  • left と right をそれぞれ1進める
  • right が配列の長さ以上になったらループを抜ける
  • temp += C[right] で新しい右端の要素をウィンドウに追加する
• 最後に points を返す

実装例

以下はPythonでの実装例です。

class Solution(object):
    def dietPlanPerformance(self, c, k, l, u):
        temp = 0
        for i in range(k):
            temp += c[i]
        right = k - 1
        left = 0
        points = 0
        while right < len(c):
            if temp < l:
                points -= 1
            elif temp > u:
                points += 1
            temp -= c[left]
            left += 1
            right += 1
            if right >= len(c):
                break
            temp += c[right]
        return points

ob1 = Solution()
print(ob1.dietPlanPerformance([6,5,0,0], 2, 1, 5))

入力

[6,5,0,0]
2
1
5

出力

0

まとめ

この問題は、固定長の区間和を繰り返し評価する典型的なスライディングウィンドウの応用例です。各ステップでウィンドウから外れる要素を引き、新しく入る要素を足すだけでよいため、計算量は O(n)、空間計算量は O(1) に抑えられます。累積和（プレフィックスサム）を使う方法でも解けますが、ウィンドウ幅 k が既知の場合はこの手法が最もシンプルで効率的です。