ケーキをどの高さで切る?

デザート店の店主が、陳列棚に高さがバラバラのケーキを立てて並べました。無料試食コーナーを作るため、カッターの刃をある高さHに合わせ、ケーキを一度に横に切ります。

するとHより高いケーキは上の部分が切り落とされ、その切れた上の部分をすべて集めて試食用ピースにします。ポイントはこれです——刃を下げるほど多く切れて集まる量は増えますが、その分、陳列用のケーキが台無しになります。

そこで試食に必要な量はちょうど満たしつつ、損傷を最小にするため 刃をできるだけ高く 置くのが目標です。

例: ケーキの高さが 15, 22, 9, 18, 30, 25 で、試食量18が必要なら? 答えは19。 (H=19なら (22-19)+(30-19)+(25-19) = 20 ≥ 18、H=20だと17で不足)

どう approach する? (核心アイデア)

最初は途方に暮れます。「どのケーキをどれだけ切るか」を直接決めようとすると、場合の数が多すぎるからです。

発想の転換 — 切る位置を選ぶのではなく、答え(刃の高さH)を先に仮定します。

•「刃が 高さHのとき 集まる量は必要量以上か?」→ これは全ケーキを一度なめて Σ max(0, 高さ - H) で 素早く判定できます。
•Hが低いと多く切れて量が多く(可能)、高いと少なく切れて量が少ない(不可能)。つまり Hについて単調です。
•単調なら? 二分探索 で「量を満たす最大のH」を見つけられます。

これが パラメトリックサーチ ——*答えそのものを二分探索する* 手法です。ソート済み配列で値を探すのではなく、答えの候補範囲(0 ~ 最も高いケーキ) を絞っていくのです。

多くの人は「二分探索=ソート済み配列で値を探す」とだけ学びます。だから *「答えを二分探索する」* 発想は最初なかなか出てきません。

でも一度 目で見れば 一気に腑に落ちます。

1. 候補の高さHを1つ決める(範囲の真ん中 = mid)

2. そのHで刃を引き、上に切られる量をすべて足す

3. 十分ならHを上げ(より高い刃に挑戦)、足りなければ下げる

4. 範囲が狭まり答えに収束する

この流れを ステップごとのアニメーション で追うと、「*だから* 二分探索なのか」が一瞬で分かります。

ケーキが棒として立ち、赤い刃の線(H)が上下に動き、切られる上の部分が一目で表示される 全工程 をステップ別の可視化で用意しました。変数の変化(lo・mid・hi、集まった量)も一緒に見えます。

パラメトリックサーチは「木を切る」「ルーター設置」「予算配分」など無数の変形でコーディングテストに登場します。一度原理を目で覚えれば、どんな姿で出ても解けます。