SRM 544 275pt : ElectionFraudDiv1

TopCoder

問題概要

一人以上が参加した投票が合った。各候補者の四捨五入された得票率が与えられるので、そのような得票率が実際に現れるには最小で何人の投票参加者がいればよいか求める問題。無理なら指摘する。

考えたこととか

  • 0がコーナーケースになりそうな予感。というか全部0のときどう返すべきなんだ？
  • いつも最初に全探索から考えるべき。
  • 分母が決まれば、得票率から得票数の範囲が得られる。
  • あとはこれが答を含んでいればよい。
  • 問題は上限だけど、多分そんな大きなことにはならないだろう。適当に回そう。
  • よさげなので書き始める。切り上げと切り下げを丁寧にやろうとしたら時間がかかった。
  • サンプルは全部通った。
  • コーナーケースっぽい0の処理を真面目に考えよう。うーん、よく分からんのでclar投げようか。
  • と思っていたら全体clarで投票者が正であることが告げられた。
  • 後はlowerやupperが負になるようなケースか？でも(10*ps[j]-5)*i + 999って下限が-5+999だから負にならない。じゃあ大丈夫そうなのでそのまま出すか。
    • 当然、下限は-5*i + 999なのでiが大きくなったところで落ちました。

acceptされたコード

#include <vector>
#include <algorithm>
using namespace std;

struct ElectionFraudDiv1 {

	int MinimumVoters(vector <int> ps) {
		const int N = ps.size();
		for(int i=1; i<=500000; ++i){
			int lower = 0, upper = 0;
			for(int j=0; j<N; ++j){
				lower += max(0, ((10*ps[j] - 5) * i + 999) / 1000);
				upper += ((10*ps[j] + 5) * i + 999) / 1000 - 1;
			}

			if(lower <= i && i <= upper){
				return i;
			}
		}
		return -1;
	}

};