効率よく盗もう (paizaランク A 相当)
方針
盗み出す財宝を適切に選んだ結果、平均価値が最大でいくつになるかを答えてください。
以上の問題文より、平均価値で二分探索ができそうです。
k個の財宝の平均価値がx以上なら、それ以下の平均価値y(y<=x)も、もちろん達成できます。なので、二分探索ができます。
k個の平均価値は問題文の定義より(v_1 + v_2 + ... + v_k) / (w_1 + w_2 + ... + w_k)で求められます。
平均価値がx以上になるなら、
(v_1 + v_2 + ... + v_k) / (w_1 + w_2 + ... + w_k) ≧ x
と表現できます。
このままだと考えにくいので、これを、財宝１つ１つの表現にできないか考えます。
財宝１つ１つの表現を目指して、式変形をします。
(v_1 + v_2 + ... + v_k) - x * (w_1 + w_2 + ... + w_k) ≧ 0
(v_1 - x*w_1) + (v_2 - x*w_2) + ... + (v_k - x*w_k) ≧ 0
こうすることで、財宝１つ１つについて、適切に選ぶことができます。
すなわち、n個財宝１つ１つについて(v_i - x*w_i)を求め、この値が大きい財宝からk個選んで、足し合わせたときに、0以上であれば、
n個の財宝から適切にk個選んだ最大の平均価値はx以上、ということです。
二分探索で、探索範囲[left, right)のとき、平均価値が mid = (left+right)/2 以上となるように 財宝を k 個選ぶことができるかどうかをチェックします。
平均価値が mid 以上となるように財宝を選べるなら、探索範囲の左端を left から mid にします。逆に選べないならば、探索範囲の右端を right から mid にします。
解き方の流れまとめ
平均価値の探索範囲[left,right]で、mid=(left+right)/2とした時、
k個の財宝を適切に選んで、最大にした平均価値が、mid以上になるか調べます。
式にすると、
(v_1 + v_2 + ... + v_k) / (w_1 + w_2 + ... + w_k) ≧ mid
が成り立つか調べるが、このままだと、k個の財宝を適切に選んで最大の平均価値にできないので、式変形して財宝１つ１つの表現にします。
(v_1 - mid*w_1) + (v_2 - mid*w_2) + ... + (v_k - mid*w_k) ≧ 0
こうすると、左辺が財宝１つ１つから求められる値になり、大きい順に並べ替えができ、大きい順に選ぶことができるようになり、適切に選んで最大の平均価値にできるようになります。
"その左辺の最大値が0以上"ならば、
"k個の財宝を適切に選んで、最大にした平均価値が、mid以上"なので、
mid以下の平均価値も、もちろん成立します。
よって、範囲の左端leftがmidになります。
また、成立しなかったら、mid以上に高い平均価値はもちろん成立しないので、右端のrightをmidにします。
以上を50回以上繰り返せば、求まります。
さらに流れまとめ
平均価値を二分探索すればよい。
平均価値の範囲[left, right]の中間をmidとした時、k個の財宝を適切に選んだ最大の平均価値を探索する。
平均価値がmid以上なら、mid以下はもちろん成り立つので、範囲の左端leftをmidに狭める。
平均価値がmid以下なら、mid以上はもちろん成り立たないので、範囲の右端rightをmidに狭める。
これを繰り返して、平均価値の境目を見つける。
ここでポイントは、k個の財宝を適切に選ぶ方法。
財宝１つ１つに何か値があって、それが大きい順にk個選べればよい。
与えられた定義(k 個の財宝の価値の和) ÷ (k 個の財宝の重さの和)がmid以上か判定する式がある。
(v_1 + v_2 + ... + v_k) / (w_1 + w_2 + ... + w_k) ≧ mid
これを変形すると、
(v_1 - mid*w_1) + (v_2 - mid*w_2) + ... + (v_k - mid*w_k) ≧ 0
が得られる。この左辺は財宝１つ１つの値の形になっているので、全部のn個の財宝の値を求めて大きい順にソートでき、大きい順に選ぶことができる。
解答コード例(Python3の場合参考)
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
const [n, k] = lines[0].split(" ").map(Number);
const W = lines[1].split(" ").map(Number);
const V = lines[2].split(" ").map(Number);
//平均価値について二分探索する
//平均価値の範囲は1 ≦ W_i ≦ 5,000 (1 ≦ i ≦ n), 1 ≦ V_i ≦ 5,000 (1 ≦ i ≦ n)より
let [left, right] = [0, 5001];
for (let i = 0; i < 100; i++) { //万全を期すため100回
/* 解説より、k個の財宝の最大の平均価値がmid以上かは、
k個の財宝のtmp_iの和が0以上か、で判定できる */
let mid = (left + right) / 2;
let tmp = Array(n).fill(0);//ここに各財宝の(v_i - x*w_i)を入れる
for (let i = 0; i <= n; i++) {
tmp[i] = V[i] - W[i] * mid;//tmp_iとする。
}
//財宝のtmp_iの値を大きい順にソート
tmp.sort((a, b) => b - a);
//k個の財宝のtmp_iの和が0以上か=k個の財宝の最大の平均価値がmid以上か
if (tmp.slice(0, k).reduce((a, b) => a + b) >= 0) {//最大の平均価値がmid以上なら
left = mid;//mid以下に最大の平均価値はない
} else { //最大の平均価値がmid以下なら
right = mid; //mid以上に最大の平均価値はない
}
}
console.log(left);