概要

この問題は、\(N\)本の花を茎の長さの差が\(D\)以下になるように\(K\)個の花束に仕分けるとき、条件を満たす最小の\(D\)を求める問題です。

考察

花束の条件は「同じ花束内の茎の長さの最大値と最小値の差が\(D\)以下」であり、\(D\)が小さいほど制約が厳しくなります。すべての花を仕分けるには\(D\)を十分大きくする必要がありますが、最小の\(D\)を見つける必要があります。

素朴なアプローチとして、\(D\)の値を0から最大値まで試す方法が考えられますが、\(D\)の取り得る範囲が最大\(10^9\)程度になるため、全探索は非現実的です。代わりに、\(D\)の値に対して二分探索を行うことで効率的に解を求めることができます。

各\(D\)の値について、その\(D\)で条件を満たすように花を仕分けられるかどうかを判定する関数が必要です。ここで重要な観察は、茎の長さでソートした後、連続する花をまとめて花束に割り当てる貪欲法が有効であることです。

アルゴリズム

1. 茎の長さの配列\(A\)をソートする
2. \(D\)の値に対して二分探索を行う
   • 下限\(low = 0\)、上限\(high = A_{max} - A_{min}\)で初期化
   • 各\(mid = (low + high)//2\)について、条件を満たすか判定
   • 条件を満たせば\(high = mid\)、そうでなければ\(low = mid + 1\)
3. 条件判定関数feasible(D)の実装
   • ソート済みの配列を先頭から走査
   • 現在の花を最小値として、\(A[j] - A[i] \leq D\)かつ花の本数が\(M\)本以下になる範囲で花束を作る
   • 花束の数が\(K\)を超えたらfalse、すべての花をカバーできたらtrueを返す

計算量

• 時間計算量: \(O(N \log (A_{max} - A_{min}))\)
  • 二分探索の反復回数が\(\log (A_{max} - A_{min})\)回
  • 各判定が\(O(N)\)で行える
• 空間計算量: \(O(N)\)
  • 配列の保存に必要なメモリ

実装のポイント

• 茎の長さのソートが最初の重要なステップです

• 条件判定関数では、貪欲にできるだけ多くの花を1つの花束にまとめることが効率的です

• 花束の本数制限\(M\)に達したら、それ以上花を追加できない点に注意します

• 二分探索の終了条件（low < high）と更新方法（low = mid + 1, high = mid）に注意します

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    A.sort()
    
    low = 0
    high = A[-1] - A[0]
    
    def feasible(D):
        count = 0
        i = 0
        bundles = 0
        
        while i < N:
            j = i
            while j < N and A[j] - A[i] <= D:
                j += 1
                if j - i == M:
                    break
            
            bundles += 1
            if bundles > K:
                return False
            count += (j - i)
            i = j
        
        return count >= N and bundles <= K
    
    while low < high:
        mid = (low + high) // 2
        if feasible(mid):
            high = mid
        else:
            low = mid + 1
            
    print(low)

if __name__ == "__main__":
    main()

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