概要

荷物を順序を保ちながらM台のトラックに分割し、最大積載量の最小値SがKより大きいかどうかを判定する問題です。

考察

この問題は、荷物の分割方法を全探索すると計算量が爆発してしまいます。重要な観察は、Sの値に対して二分探索が適用できることです。Sの候補値Xを決めたとき、「各トラックの積載量をX以下に抑えながらM台以内で全ての荷物を運べるか」を貪欲法でチェックできます。このチェック関数を用いて二分探索することで、効率的にSを求めることができます。

アルゴリズム

1. 二分探索でS（最大積載量の最小値）を求めます
2. 探索範囲の下限は荷物の最大値（1台に1個しか積めない場合）、上限は十分大きな値とします
3. 各候補値midに対してチェック関数を実行：
   • 荷物を先頭から順にトラックに積み、積載量がmidを超えないように貪欲に追加
   • 超える場合は新しいトラックを使用
   • M台以内で全ての荷物を運べればTrue、そうでなければFalse
4. 求めたSとKを比較し、S > Kなら”Yes”、そうでなければ”No”を出力

計算量

• 時間計算量: \(O(N \log(\sum A_i))\)
  • 二分探索の反復回数は \(O(\log(\sum A_i))\) 回
  • 各反復で貪欲法によるチェックに \(O(N)\) 時間
• 空間計算量: \(O(N)\)
  • 荷物の重さを格納する配列のみ使用

実装のポイント

• 二分探索の初期値設定：下限は荷物の最大値、上限は十分大きな値（\(10^{18}\)）に設定

• 貪欲法のチェックでは、現在のトラックの積載量が制限値を超えるかどうかを逐次判定

• トラックの使用台数がMを超えた時点で即座にFalseを返すことで効率化

• 整数のオーバーフローに注意（Kや積載量が最大\(10^{15}\)まで大きくなる可能性あり）

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    left = max(A)
    right = 10**18
    
    def check(limit):
        count = 1
        current = 0
        for a in A:
            if current + a <= limit:
                current += a
            else:
                count += 1
                current = a
                if count > M:
                    return False
        return True
    
    low = left
    high = right
    while low < high:
        mid = (low + high) // 2
        if check(mid):
            high = mid
        else:
            low = mid + 1
    S = low
    
    if S > K:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。