Google Code Jam 2012 Round1B 問題A

その他 過去問

問題

N人が審査員およびオーディエンスによって審査される。
各人は審査員からのポイントJ[i]が与えられる。
オーディエンスからのポイントは、その人への投票の割合Y[i](0〜100%)を審査員ポイントXの合計にかけたものX*Y[i]になる。
すなわち、その人のポイントはJ[i]+X*Y[i]となる。

N人のうち、最小ポイントの人は脱落する。
ただし、同じ最小ポイントの人が複数人いた場合は、脱落者はいない。
各人が脱落しないために必要なオーディエンスからの投票の割合の最小値を求めよ。

考え方

2分探索。

最小ポイント値がわかれば、その値に必要な投票率を出せる。
各人の投票率の合計が100%になるまで2分探索。

反省

Greedyな感じで解いた。