UTPC2012 : E - 選挙

ここから配点が上がって難易度増加。
なんとかこれはノーヒントで解けました。
http://utpc2012.contest.atcoder.jp/tasks/utpc2012_05

最大剰余方式の選挙で、得票数と最低当選議席数が与えられたとき、総議席数を答えるもの。
剰余計算により、剰余に応じて±1程度当選者数がずれるのを考慮しないといけない。

ただ、解法は割と単純。
まず、剰余分を無視して最低総議席数を求める。
最低総議席の和がSとすると、Bi*S/Aiが各党の議席となる。

よって、上記各議席の最大値から、100000(=N*Ai)少ない総議席から、総議席を1ずつ増やしながら議席数をシミュレーションすればよい。
探索範囲は100000、政党数100なのでなんとか間に合う。

int N;
ll A[200],B[200];
ll TP,S;

int ok(ll tp) {
	int i;
	ll C[101];
	ll tpt=tp;
	
	vector<pair<ll,int> > mod;
	
	FOR(i,N) {
		tpt-=A[i]*tp/S;
		C[i]=A[i]*tp/S;
		if(C[i]+1<B[i]) return 0;
		
		mod.push_back(make_pair(-((A[i]*tp)%S),i));
	}
	sort(mod.begin(),mod.end());
		
	FOR(i,tpt) C[mod[i].second]++;
	FOR(i,N) if(C[i]<B[i]) return 0;
	return 1;
	
}

void solve() {
	int x,y,z,i,j,rr,TM;
	ll p,tp;
	
	N=GETi();
	S=TP=0;
	FOR(i,N) {
		A[i]=GETi();
		B[i]=GETi();
		S+=A[i];
		TP+=B[i];
	}
	
	p=0;
	FOR(i,N) {
		if(B[i]==0) continue;
		p = max(p, B[i]*S/A[i]);
	}
	
	for(tp=max(TP,p-100000);tp<=p+200000;tp++) {
		if(ok(tp)) {
			_P("%lld\n",tp);
			return;
		}
	}
	return;
}

まとめ

これも何とか解法が思いついてよかった。