LeetCode 1011. Capacity To Ship Packages Within D Days 再び

はじめに

前回投稿したタイトルのこの問題。
最初に取り組んだ時は二分探索ではない方法でやろうとしました。
ずっと解けずに「Time Limit Exceeded」。
私の記事の大半を占めるTLEが出続けていました。

でも、諦めずにコード書き続けたらAcceptedになったので
嬉しなって投稿します。

考え方

問題そのものは前回の記事見てもらうとして、考え方です。

出発点は、以下の式から考えました。

$総重量 = 1日の積載量 \times 積載日数$

この式を $1日の積載量$ について解くと

$1日の積載量 = \frac{総重量}{積載日数} $

となり、総重量はsum(weights)で一定なので、
反比例の式になる。

ということは、積載日数daysが最大のとき、$1日の積載量$が最小になる。

なので、最大積載量を積載日数で割ったものが$1日の積載量$最小なので、
そこから積載できなければ、$1日の積載量 を +1$していく。

解答例

1011. Capacity To Ship Packages Within D Days

class Solution(object):
    def shipWithinDays(self, weights, days):
        # days以内でさばけるか
        def can_ship_within_days(capacity_a_day):
            spend_days = 1
            total_weight_a_day = 0
            for weight in weights:
                if total_weight_a_day + weight > capacity_a_day:
                    spend_days += 1
                    total_weight_a_day = weight
                else:
                    total_weight_a_day += weight

                if spend_days > days:
                    return False
            return True

        total_weight = sum(weights)
        avg_a_day = max(max(weights), total_weight // days)

        # 最小値でdays以内にさばけるか。さばけないなら1日あたりの積載量+1
        while not can_ship_within_days(avg_a_day):
            avg_a_day += 1

        return avg_a_day

おわりに

問題文やヒントにbinary searchって書かれているので、基本的には二分探索を使って解く問題です。

天邪鬼な部分が出てしまい、どうしても二分探索使わずに解きたかったです。
個人的には解けて満足です。
問題によっては解けないこともあると思います。