ケーブル切断とは？
長さがバラバラのケーブルを数本、すべて同じ長さに切って 一定数（K本）以上の切れ端を作りたいとき、「1切れの最大の長さはいくらか？」を求める問題です。
核心は、答え（切れ端の長さ）そのものを二分探索する という点です。配列から値を探す通常の二分探索とは違い、「可能な長さの範囲」を半分ずつ絞って答えを見つけます。この技法を パラメトリック探索（Parametric Search） と呼びます。
なぜ二分探索が使えるの？
切れ端の長さをLとすると、作れる本数は次のとおりです。
本数(L) = ⌊ケーブル₁ / L⌋ + ⌊ケーブル₂ / L⌋ + ... + ⌊ケーブルₙ / L⌋- •Lを 小さく すると本数は決して減りません → 単調性（monotonicity）
- •したがって「本数 ≥ K」を満たすLの境界が1か所だけ存在します
- •その境界を二分探索で見つければ完了です
この単調性がパラメトリック探索の前提条件です。最適化問題（最大の長さは？）を 決定問題（この長さでK本作れるか？）に変えるのが核心の発想です。
動作原理
ステップ1. 探索範囲を決めます。lo = 1、hi = 最も長いケーブルの長さ。
ステップ2. mid = (lo + hi) / 2 を切れ端の長さの候補にします。
ステップ3. midで切ったときに作れる本数を数えます（決定関数）。
- •本数 ≥ K → 可能！候補として保存し
lo = mid + 1（もっと長く挑戦） - •本数 < K → 不足！
hi = mid - 1（短く切ってもっと作る）
ステップ4. lo > hi になるまで繰り返すと、最後の候補が答えです。
例で追いかける
ケーブル [57, 42, 36, 20]、必要本数 K = 3 のとき：
| 切れ端の長さ L | 本数の計算 | 結果 |
|---|---|---|
| 29 | 1+1+1+0 = 3 | 可能 → lo=30 |
| 43 | 1+0+0+0 = 1 | 不足 → hi=42 |
| 36 | 1+1+1+0 = 3 | 可能 → lo=37（候補） |
| 39 | 1+1+0+0 = 2 | 不足 → hi=38 |
| 37 | 1+1+0+0 = 2 | 不足 → hi=36 |
lo(37) > hi(36) となり終了。答えは36 です。L=37だと2本しか作れず不可能でした。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(N log L) |
| 空間 | O(1) |
候補の長さを約log L回試し、毎回N個のケーブルを合算するのでO(N log L)です。ケーブルの長さが10億でも約30回の反復で十分です。
よくあるミス
- •loを0から開始：長さ0では割れません。必ず
lo = 1から。 - •本数のオーバーフロー：ケーブルが多く長いと本数が非常に大きくなります。64ビット整数(long)で累積しましょう。
- •境界更新のミス：「可能なら長く(lo=mid+1)」「不足なら短く(hi=mid-1)」の方向を取り違えると無限ループや誤答になります。
AlgoNoteで直接確認しましょう
ケーブル切断で切れ端の長さが各ステップでどのように絞られるか、各長さで何本取れるかを、AlgoNoteの可視化でステップごとに確認できます。