ひとりで勝手にはじめた蟻本読書会 二分探索法 lower_bound と upper_bound 蟻本読書会 の続きです。
～を満たす最大値（または最小値）
二分探索法でパイプを切る問題を解くにもあるように、「～を満たす最大値（または最小値）を求めよ」という問題に対して、解 x を仮定して可能かを判定する、二分探索法でその最大値や最小値を求めるというのはよくあるテクニックです。
高橋君は赤い花を R 本、青い花を B 本持っています。高橋君は次の 2 種類の花束を作ることができます。
x 本の赤い花と 1 本の青い花からなる花束
1 本の赤い花と y 本の青い花からなる花束高橋君が作ることのできる花束の個数の最大値を求めてください。すべての花を使い切る必要はありません。
入力されるデータ
R B
x y1 ≦ R，B ≦ 10^18
2 ≦ x，y ≦ 10^9
二分探索法で「K 個の花束を作ることができるか？」という Yes / No 問題を考えます。花束を作るためには赤い花と青い花が少なくとも 1 本ずつ必要なので、とりあえず赤い花と青い花を K 本ずつ減らします。そのうえで、「x 本の赤い花と 1 本の青い花からなる花束」を作るためにはさらに赤い花が x – 1 本必要なので、赤い花束は (R – K) / (x – 1) 個（端数切り捨て）作ることができます。同様に「1 本の赤い花と y 本の青い花からなる花束」は (B – K) / (y – 1) 個作ることができます。
ここで注意が必要なのは分子が負数になる場合は、K 個の花束を作ることは絶対にできないということです。これを見落としていて何回やっても数件の WA が出てしまい、あーでもないこーでもないで無駄に時間を浪費してしまいました。
二分探索するにあたっての上限と下限ですが、下限は 0 で問題ありません。上限は R，B の上限が 10^18 なのでその合計値にしています。両者の中間値を計算するときに (left + right) / 2 ではオーバーフローするケースがあるのですが、この場合は問題ありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { long R, B; { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); R = vs[0]; B = vs[1]; } long x, y; { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); x = vs[0]; y = vs[1]; } long left = 0; long right = (long)Math.Pow(10, 18) * 2 + 1; long ans = 0; while (true) { long mid = (left + right) / 2; if (Check(R, B, x, y, mid)) left = mid; else right = mid; if (right - left <= 1) { ans = left; break; } } Console.WriteLine(ans); } // 全部で R 本の赤い花と B 本の青い花から // x 本の赤い花と 1 本の青い花からなる花束 // 1 本の赤い花と y 本の青い花からなる花束 // 合計 mid 個を作ることができるか？ static bool Check(long R, long B, long x, long y, long mid) { long r = R; long b = B; r -= mid; b -= mid; if(r < 0 || b < 0) // この場合もできないので注意が必要 return false; long c1 = r / (x - 1); long c2 = b / (y - 1); if (c1 + c2 >= mid) return true; else return false; } } |
最小値の最大化 (最大値の最小化)
最小値の最大化問題は二分探索法でうまく解けることがあります。
左右の長さが L [cm] のようかんがあります。
N 個の切れ目が付けられており、左から i 番目の切れ目は左から A_i [cm] の位置にあります。あなたは N 個の切れ目のうち K 個を選び、ようかんを K + 1 個のピースに分割したいです。そこで「K + 1 個のピースのうち、最も短いものの長さ（cm 単位）」を スコア とします。
スコアが最大となるように分割する場合に得られるスコアを求めてください。
入力されるデータ
N L
K
A_1 A_2 … A_N1 ≦ K, N ≦ 100000
0 ＜ A_1 ＜ A_2 ＜ … ＜ A_N ＜ L ≦ 10^9
二分探索法ですべての長さを mid 以上にして K+1 個に切り分けられるか試してみます。right と left の差が1になったら終了です。left が求めるスコアとなります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
using System; using System.Collections; using System.Collections.Generic; using System.Linq; class Program { static void Main() { long N, L; { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); N = vs[0]; L = vs[1]; } long K = long.Parse(Console.ReadLine()); List<long> values = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToList(); values.Add(L); long left = 0; long right = L; long ans = 0; while (right - left > 1) { long mid = (right + left) / 2; // すべての長さを mid 以上にして K+1 個に切り分けられるか試してみる long len = 0; // 長さ long cnt = 0; // 切り分けた個数 bool ok = false; // できたかどうか？ long start = 0; // 切り分けの開始地点 foreach (long v in values) { len = v - start; // 切り分けの開始地点からの長さ（mid 以上であれば OK） if (len >= mid) // mid 以上であるので 1 ピース完成 { cnt++; // 切り分けた個数をインクリメント。次のピースを作る start = v; len = 0; } if (cnt > K) // mid 以上にして K+1 個に切り分けられることが確認できた { ok = true; break; } } if (ok) left = mid; // 切り分けられる場合 else right = mid; // 切り分けられない場合 } Console.WriteLine(left); } } |
