二分探索:最小値の最大化(4題)

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
この本(通称:蟻本)の章末で紹介されている練習問題をひたすらといている。

第3章の章末に入った。

二分探索。最小値の最大化である。一般的には、条件 C(x) を満たす最大の x を求めたりするときに二分探索を使う。C(x) のところだけ個別に実装して、二分探索 bi_search() は使いまわせる。

POJ3258:River HopScotch

3258 -- River Hopscotch

問題概要

スタートの岩からゴールの岩まで距離 L だけ離れている。その二つの岩の間に、 N 個の岩がある。各岩はスタートの岩から距離 Di のところにある。これらの岩から M 個を取り除いて、隣り合う岩の距離の最小値を最大化する。
1 <= L <= 1,000,000,000
0 <= N <= 50,000
0 <= M <= N
0 < Di < L

解法

条件 C(x) を満たすような x を最大化するには二分探索する。
問題は条件 C(x) だが、ここでは以下のようになる。
C(x) : 岩を M 個取り除いて、隣り合う2つの岩の距離をどれも x 以上にできるかどうか
C(x) の判定は貪欲法で O(N) 時間でいける。


POJ3273: Monthly Expense

3273 -- Monthly Expense

問題概要

N 個の整数からなる数列が与えられる。これを M 個の区間に分ける。区間は1つ以上の連続する項からなる。区間にある項の和の最大値を最小化するように区間を定めよ。
1 <= N <= 100,000

解法

区間にある項の和の最大値が x 以下となるような区間分けが可能かどうかは、 O(N) で判定できる。そのような条件を満たす最小の x を探索するには、二分探索で OK 。


POJ3104:

3104 -- Drying

問題概要

洗濯物が n 個ある。それぞれの洗濯物には水分が a[i] 含まれている。自然乾燥だと、洗濯物は1分で1だけ水分が減る。乾燥機を使うと1分で k だけ水分が減る。乾燥機は一度に1つの洗濯物にしか使えない。洗濯物がすべて乾くまでの時間を最小化せよ。

解法

x 分以下で洗濯物を乾かせるかどうかの判定は O(n) でできる。乾燥機が x 回使えるので、それぞれの洗濯物が x 分以下で乾くように乾燥機を使ったとして、乾燥機の使用回数が x を超えないかどうかをチェックすればよい。あとは x の最小値は二分探索で。
あるいは、別の解法で、単純な貪欲法でも解けそう。「毎分、水分が最も多く残っている洗濯物を乾燥機に放り込む」というルールで乾かせばいいと思う。


POJ3045: Cow Acrobats

3045 -- Cow Acrobats

問題概要

N 頭の牛が垂直に重なってタワーを作る。牛 i には重さ W[i] と強さ S[i] がある。牛 i の危険度は、 (上に乗っている牛の重さの和) - (牛 i の強さ) で計算される。牛の危険度の最大値を最小化せよ。

解法

危険度の最大値が x 以下、つまりすべての牛の危険度を x 以下にできるかどうかの判定 C(x) は、O(N log N) でできる。次のように考えればよい。それぞれの牛 i について、危険度が x 以下であるなら、
(上に乗れる牛の重さの和) <= (牛 i の強さ) + x
が成立する。
牛を下から積み上げることにする。牛を強い順に見ていきその位置の重さにたえられる牛をまずは集める。そして、「その位置の重さにたえられる牛の中で体重の最も大きな牛を配置する」というルールで順に牛を配置する。これで C(x) が判定できる。あとは C(x) を満たす x のうち最小の値を二分探索で求める。