たのしく二分探索: 競プロ典型 90 問 001 - Yokan Party（★4）
問題
解説
L cmのようかんをK+1個に分割するとき，分割したようかんの大きさの最小値をできるだけ大きくする問題です．
最小値の最大値が求められるような場合，二分探索が有効です．
二分探索を簡単にイメージするためには，次の例を考えることが効果的です(ご存じの場合読み飛ばすことを推奨します)．
- 人の年齢をの最小回数の質問で正確に当てたい．
- 簡単にするために質問者Aは対象者Bの年齢が20歳以上68歳未満であるとわかっていることにします．
- 今回の例では対象者Bの年齢を34歳とします．
- 次のように当てます．
- A「Bさんの年齢は44歳以上ですか？」( (20 + 68)/ 2)
- B「いいえ」(ここでBさんの年齢は20歳以上44歳未満であることが確定します)
- A「Bさんの年齢は32歳以上ですか？」( (20 + 44)/ 2)
- B「はい」(ここでBさんの年齢は32歳以上44歳未満であることが確定します)
- A「Bさんの年齢は38歳以上ですか？」( (32+ 44)/ 2)
- B「いいえ」(ここでBさんの年齢は32歳以上38歳未満であることが確定します)
- A「Bさんの年齢は35歳以上ですか？」( (32+ 38)/ 2)
- B「いいえ」(ここでBさんの年齢は32歳以上35歳未満であることが確定します)
- A「Bさんの年齢は33歳以上ですか？」( (32+ 35)/ 2 (小数点切り捨て))
- B「はい」(ここでBさんの年齢は33歳以上35歳未満であることが確定します)
- A「Bさんの年齢は34歳以上ですか？」( (33+ 35)/ 2)
- B「はい」(ここでBさんの年齢は34歳以上35歳未満であることが確定して，それは一意に定まるため，34歳であることが確定します)
この例では20歳以上68歳未満の48通りを半分ずつ削ることで，効率的に探索します．これが二分探索です．
半分ずつ削るため，探索空間をNとすると O(logN)です．
ようかんの問題では，スコアの最小値を0，スコアの最大値をL*1と考えて，次の判定問題を考えます．
- ようかんが目標スコアより小さくならないように切っていき，K+1個に分割可能か？
分割可能かは貪欲法を用いることで判定可能です．片端から目標スコア以上になるように切れる部分を狙って切ることを繰り返すことで十分です．
二分探索の実装では，スコアの最小値を表す変数leftと，スコアの最大値+1を表す変数rightを用いるのが便利です．
目標スコア(範囲の中間点)は(left + right) / 2で求めることができ，それが達成できればright = (left + right) / 2に，達成できなければleft = (left + right) / 2とします．範囲が一意に定まるまでループさせます．
right - left = 1のとき，範囲が一意に定まったとして，leftが求める値になります．そのため，while(right - left > 1) を用いましょう．
計算量は二分探索でlog(L)，各ステップの判定でN*2となるため，全体としてO(N log(L) )です．十分高速です．
簡単な動作例
図1の例を用います．K = 2とします．そのため，3分割することが目標です．
- [left = 0, right = 24] ⇒ mid = 12で，3分割できないため，right = midとする．
- [left = 0, right = 12] ⇒ mid = 6で，3分割できるため，left = midとする(11の切れ目と18の切れ目で達成できます)．
- [left = 6, right = 12] ⇒ mid = 9で，3分割できないため，right = midとする．
- [left = 6, right = 9] ⇒ mid = 7で，3分割できないため，right = midとする．
- [left = 6, right = 7] ⇒ right - left = 1であるため，答えとしてleft = 6を出力する．
ソースコード例(C++)
知的文章を書く能力が欲しいです
