SRM544 Div1 Easy - ElectionFraudDiv1

自力で解けなかった😰

問題

n人の候補者がいる選挙が行われ、i人目の得票率は四捨五入するとp[i]パーセントだったらしい
しかしこの情報が嘘である可能性がある
この得票率になるような投票人数と投票の仕方が存在する場合は投票人数の最小値を、存在しない場合は-1を返せ

1 <= n <= 50
0 <= p[i] <= 100

解法

答えの最大値はたかだか1000になる(らしい)から全部試せばいい
投票人数がm人のとき、得票率がp[i]になるような得票数の下限と上限それぞれの総和(l,r)を求め、l<=m<=rとなっていればok
判定は愚直にやってもO(nm)でできるからトータルでO(nm^2) (m=1000) で間に合う

editorialにも書いてるけど判定を二分探索でやれば更に高速になる
そうすると答えの上限が1000ってことがわからなくても25000くらいまで全探索できるようになって安心感が得られるらしい笑

↓今証明読むのしんどいから今度読むリストに追加
http://apps.topcoder.com/wiki/display/tc/SRM+544

class ElectionFraudDiv1 {
public:
	int MinimumVoters(vector<int> p) {
		reps(m,1,1010) {
			int l = 0, r = 0;
			each(i,p) {
				int mn = inf, mx = 0;
				rep(j,m+1) if ((int)round(100.*j/m)==i) chmin(mn,j), chmax(mx,j);
				if (mn==inf) {
					l = 1<<30;
					break;
				}
				else l += mn, r += mx;
			}
			if (l<=m && m<=r) return m;
		}
		return -1;
	}
};