ひとりで勝手にはじめた蟻本読書会 二分探索法 可能となるような最大値・最小値を求める 蟻本読書会 の続きです。
基本問題
二分探索法は平均最大化する問題を解くときにも使えます。
paiza 博物館に、n 個の財宝が展示されています。各財宝の価値は V_1, V_2, …, V_n であり、重さは W_1, W_2, …, W_n です。怪盗であるあなたは、paiza 博物館からちょうど k 個の財宝を盗み出そうとしています。
盗み出す財宝を適切に選んだ結果、平均価値が最大でいくつになるかを答えてください。k 個の財宝の平均価値は、(k 個の財宝の価値の和) ÷ (k 個の財宝の重さの和) で定義します。
答えは整数になるとは限りません。相対誤差または絶対誤差が 10^-6 (0.000001) 以下であれば正解とみなされます。
n k
W_1 W_2 … W_n
V_1 V_2 … V_n（ただし、
1 ≦ n ≦ 2,000
1 ≦ k ≦ n
1 ≦ W_i ≦ 5,000
1 ≦ V_i ≦ 5,000 ）
二分探索法で mid ≦ k 個の財宝の平均価値となる mid の最大値を探します。
財宝の平均価値は、(k 個の財宝の価値の和) ÷ (k 個の財宝の重さの和) で定義されるので、(V[0] + V[1] + … + V[n-1]) / (W[0] + W[1] + … + W[n-1]) ≧ mid です。
これは以下のように変形できます。
V[0] + V[1] + … + V[n-1] ≧ mid * (W[0] + W[1] + … + W[n-1])
V[0] + V[1] + … + V[n-1] ≧ mid * W[0] + mid * W[1] + … + mid * W[n-1]
(V[0] – mid * W[0]) + (V[1] – mid * W[1]) + … + (V[n-1] – mid * W[n-1]) ≧ 0
V[i] – mid * W[i] をそれぞれ計算して降順（大きい順）にソートして先頭から k 個取り、その合計が 0 以上であれば、mid ≦ k 個の財宝の平均価値 であると言えます。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] W = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] V = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); double left = 0; double right = 5001; // 問題文より価値の最大値が 5000 なので・・・ double error = Math.Pow(10, -6); // 許容される誤差 while (right - left > error) { double mid = (right + left) / 2; List<double> d = new List<double>(); for (int i = 0; i < N; i++) d.Add(V[i] - W[i] * mid); if (d.OrderByDescending(_ => _).Take(K).Sum() >= 0) left = mid; else right = mid; } Console.WriteLine(left); } } |
食塩水が入った容器が N 個あります。 容器には 1 から N までの番号がついています。
i 番の容器には濃度 p_i パーセントの食塩水が w_i グラム入っています。 高橋君は、K 個の容器を選び、選んだ容器の中に入っている食塩水をすべて混ぜ合わせることにしました。高橋君の混ぜた食塩水の濃度として考えられる最大値を求めてください。入力されるデータ
N K
w_1 p_1
w_2 p_2
…
w_N p_N（ただし、1 ≦ N, K ≦ 1000
1 ≦ w_i ≦ 10^9, 0 ≦ p_i ≦ 100 ）
食塩水の濃度は 食塩の質量 / 食塩の質量 * 100 です。したがって、食塩の質量 = 食塩水の濃度 * 食塩水の質量 / 100 です。
また混ぜ合わせた n 個の食塩水の濃度は (P[0] * W[0] + P[1] * W[1] + … + P[n-1] * W[n-1]) / (W[0] + W[1] + … + W[n-1]) になるので、これが mid を超えるかどうかは (P[0] * W[0] – mid * W[0]) + (P[1] * W[1] – mid * W[1]) + … + (P[n-1] * W[n-1] – mid * W[n-1]) が 0 以上になるかどうかで決まります。そこで二分探索法で、W[i] * (P[i] – mid) を計算して降順にソートし先頭から K 個取ったものの総和が 0 以上になるかを調べます。
|
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 |
using System; using System.Collections; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } int[] W = new int[N]; int[] P = new int[N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); W[i] = vs[0]; P[i] = vs[1]; } double left = 0; double right = 100; double error = Math.Pow(10, -7); while (right - left > error) { // 平均をmid以上にできるか？ double mid = (right + left) / 2; List<double> d = new List<double>(); for (int i = 0; i < N; i++) d.Add(W[i] * (P[i] - mid)); if (d.OrderByDescending(_ => _).Take(K).Sum() >= 0) left = mid; else right = mid; } Console.WriteLine(left); } } |
応用問題
N 枚のカードがあり、i(1 ≦ i ≦ N) 番目のカードには整数 A_i が書かれています。
高橋君は、これらのカードから好きな枚数選びます。ただし、各 i(1 ≦ i ≦ N – 1) について、i 番目のカードと i + 1 番目のカードの少なくとも一方を選ぶ必要があります。
以下の値を求めてください。
選んだカードに書かれた整数の平均値としてあり得る最大値
選んだカードに書かれた整数の中央値としてあり得る最大値ただし n 個の整数の中央値は、それらのうち小さい方から数えて Ceiling(n / 2) 番目であるものとします。ここで、Ceiling(x) は x 以上の最小の整数を表します。
入力されるデータ
N
A_1 A_2 … A_N（ただし、2 ≦ N ≦ 10^5, 1 ≦ A_i ≦ 10^9 ）
X の平均値は、(X[0], X[1], …, X[n-1]) / N で定義されるので、X の平均値 ≧ mid は以下のように変形できます。
X[0] + X[1] + … + X[n-1] / N ≧ mid
X[0] + X[1] + … + X[n-1] ≧ mid * N
(X[0] – mid) + (X[1] – mid) + … + (X[n-1] – mid) ≧ 0
B[i] = A[i] – mid とすると
B[0] + B[1] + … + B[n-1] ≧ 0
中央値について
「X[0], X[1], …, X[n-1] の中央値が mid 以上」とは「X[i] のうち mid 以上のものの個数が mid 未満のものの個数より多い」と同値です。
C[i] を A i ≧ K なら 1、そうでないなら -1 とおき、選んだカードに対応する C[i] の総和の最大値が正かどうか判定すればよいです。
i 番目のカードと i + 1 番目のカードの少なくとも一方を選ぶという条件で A[i] の総和の最大値を求めるにはどうすればよいのでしょうか？ 動的計画法で以下のようにして求めます。
f[k] : k 番目のカードまで選ぶかどうか決め、かつ k 番目のカードを選ぶときの A[i] の総和の最大値
g[k] : k 番目のカードまで選ぶかどうか決め、かつ k 番目のカードを選ばないときの A[i] の総和の最大値
と定義します。
f[0] = 0;
g[0] = 0;
あとは、
f[k] = max(f[k-1], g[k-1]) + A[k-1]
g[k] = f[k-1]
と計算していって最後に max(f[n], g[n]) を返します。計算量は O(N) です。
|
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 67 68 69 70 |
using System; using System.Collections; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Console.WriteLine(GetMaxOfAverage(A)); Console.WriteLine(GetMaxOfMedian(A)); } // i 番目 または i + 1 番目の少なくとも一方を選ぶという条件で配列の総和の最大値を求める static double GetMaxOfSums(double[] arr) { double[] f = new double[arr.Length + 1]; double[] g = new double[arr.Length + 1]; for (int i = 1; i <= arr.Length; i++) { f[i] = Math.Max(f[i - 1], g[i - 1]) + arr[i - 1]; g[i] = f[i - 1]; } return Math.Max(f[arr.Length], g[arr.Length]); } static double GetMaxOfAverage(int[] A) { double left = 0; double right = Math.Pow(10, 9) + 1; double error = Math.Pow(10, -3); while (right - left > error) { // 平均をmid以上にできるか？ double mid = (right + left) / 2; double[] B = A.Select(_ => _ - mid).ToArray(); if (GetMaxOfSums(B) >= 0) left = mid; else right = mid; } return left; } static double GetMaxOfMedian(int[] A) { int left = 0; int right = (int)Math.Pow(10, 9) + 1; while (right - left > 1) { int mid = (right + left) / 2; //C[i] を A i ≧ K なら 1、そうでないなら -1 double[] C = A.Select(_ => _ >= mid ? 1.0 : -1.0).ToArray(); if (GetMaxOfSums(C) > 0) left = mid; else right = mid; } return left; } } |
