Pythonで同じ長さのリボンをk本切り出せる最大の長さを求めるプログラム

正の整数のリスト(各リボンの長さを表します)と整数 k が与えられます。リボンは何回でも切ることができるので、長さ r のリボンをちょうど k 本作れるような最大の r を求めてください。そのような解が存在しない場合は -1 を返します。

たとえば、入力が ribbons = [1, 2, 5, 7, 15]、k = 5 の場合、出力は 5 になります。長さ 15 のリボンを長さ 5 の 3 本に切り分け、長さ 7 のリボンは長さ 2 と 5 に切り分けます。さらに長さ 5 のリボンがもう 1 本あるため、合計で長さ 5 のリボンが 5 本手に入ります。

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

この問題は二分探索(バイナリサーチ)を使うことで効率的に解けます。ポイントは、「ある長さ mid で切り出したときの本数の合計が k 以上であれば、その長さは実現可能」という判定が単調であることです。つまり、短い長さほど多くのリボンが作れ、長い長さほど少なくなるため、実現可能な最大の長さを二分探索で絞り込むことができます。

アルゴリズムの手順

• left を 0、right をリボンの長さの最大値に初期化する
• left < right の間、以下を繰り返す
  • mid := (left + right + 1) // 2(切り捨てだが +1 することで探索が右寄せになり、無限ループを防ぐ)
  • sum(ribbonLen // mid for each ribbonLen) が k 以上なら、その長さは実現可能なので left := mid とする
  • そうでなければ right := mid - 1 とする
• ループ終了後、left が 0 以外なら left を返す
• それ以外は -1 を返す

計算量は、各判定に O(n)(n はリボンの本数)、二分探索に O(log m)(m は最長のリボンの長さ)かかるため、全体で O(n log m) となります。

実装例(Python)

以下のコードで実際の動きを確認してみましょう。

def solve(ribbons, k):
   left = 0
   right = max(ribbons)
   while left < right:
      mid = (left + right + 1) // 2
      if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
         left = mid
      else:
         right = mid - 1
   if left:
      return left
   return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

入力

[1, 2, 5, 7, 15], 5

出力

5