Code Festival Team Relay E White and Blue

例の表

https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0

所感

さんすうだってわかっていれば行ける系

問題概要

N人の人間がいて、i番目の人はwiの白表とbiの青票を持っている。賛成の場合はwiの白票をすべて、反対の場合はbiの青票をすべて投票する。
白票の割合がP%以上で法案が可決されるとき、可決に必要な最低人数を求めよ。

取った方針

議員の影響力はw[i] + b[i] で求められる気がするのでソートして貪欲をした。普通に嘘なので死亡(同数のときの順位付けが不可能)

正しい方針(解説の方針)

投票された白票の総数をW、青票の総数をBとおく。
可決の条件はW/(W+B) >= P/100 で表すことができ、これを変形すると(100-P)*W - P*B >= 0 となる。 これは、白票のスコアを100 - P、青票のスコアを-P としたとき、投票されたスコアの総和が0以上ならば法案が可決されることを意味する。
この時、議員の影響力は(100 - P)*w[i] + P*b[i]で表せるので、全員反対としたあとに一人ずつ影響力が大きい順に賛成としていくと求まる。

得られた知見

・解の条件を数式にできるならする

解くのに必要な要素

・評価値を計算 -> 貪欲
・解の条件を数式にして変形

周辺調査によって得られた知見

特になし