Pythonでm個の花束を作るのに必要な最小日数を求めるアルゴリズム（二分探索）

問題概要

整数型の配列 bloomDay と、2つの値 m、k が与えられます。庭には n 本の異なる花があり、i 番目の花は bloomDay[i] 日目に開花します。1つの花束を作るには、隣り合う k 本の花が必要で、各花は1つの花束にしか使用できません。

このとき、m 個の花束を作るために待つ必要のある最小日数を求めてください。もし m 個の花束を作ることが不可能な場合は -1 を返します。

入力例と動作の確認

たとえば、入力が bloomDay = [5,5,5,5,10,5,5]、m = 2、k = 3 の場合、出力は 10 になります。これは、2個（m = 2）の花束を作る必要があり、それぞれに3本の花が必要だからです。

• 5日目の時点：[x, x, x, x, _, x, x] — 最初に咲いた3本の花で1つの花束は作れますが、2つ目の花束はまだ作れません。
• 10日目の時点：[x, x, x, x, x, x, x] — すべての花が咲き、2つの花束を複数の組み合わせで作れるようになります。

解法のアプローチ：二分探索

この問題は「答えとなる日数」に対して二分探索を適用することで効率的に解けます。ある日数 x 日目に m 個の花束が作れるならば、それ以降の日でも必ず作れるという単調性が成り立つためです。

アルゴリズムの手順

1. n を bloomDay のサイズとします。
2. m * k > n の場合、花の総数が足りないため -1 を返します。
3. 関数 possible(x) を定義します。「x 日目までに m 個の花束が作れるか」を判定する関数です。
4. possible() の内部では以下のように処理します。
   • count := 0、bouquets := 0 で初期化します。
   • bloomDay の各要素 d について、d <= x なら count を +1 し、count が k に達したら bouquets を +1 して count を 0 に戻します。
   • d > x の場合は count を 0 にリセットします（花の連続性が途切れるため）。
   • 最後に bouquets >= m なら true、そうでなければ false を返します。
5. メイン処理では以下を実行します。
   • left := 0、right := max(bloomDay) + 1 と初期化します。
   • left < right の間、mid := (left + right) / 2 として、possible(mid) が true なら right := mid、false なら left := mid + 1 と更新します。
   • ループ終了後、possible(left) が true なら left を返し、そうでなければ left + 1 を返します。

Pythonでの実装例

def solve(bloomDay, m, k):
    n = len(bloomDay)
    if m * k > n:
        return -1
    def possible(x):
        count = 0
        bouquets = 0
        for d in bloomDay:
            if d <= x:
                count += 1
                if count == k:
                    bouquets += 1
                    count = 0
            else:
                count = 0
        return bouquets >= m
    left, right = 0, max(bloomDay) + 1
    while left < right:
        mid = (left + right)//2
        if possible(mid):
            right = mid
        else:
            left = mid + 1
    if possible(left):
        return left
    else:
        return left + 1

bloomDay = [5,5,5,5,10,5,5]
m = 2
k = 3
print(solve(bloomDay, m, k))

入力

[5,5,5,5,10,5,5], 2, 3

出力

10

計算量について

判定関数 possible() は配列を1回走査するだけで O(n)、二分探索の繰り返し回数は最大日数を M とした場合に O(log M) であるため、全体の時間計算量は O(n log M) となります。空間計算量は追加のデータ構造を使用しないため O(1) です。全探索（O(n × M)）に比べて大幅に高速化できるのがこの手法の利点です。