MemSQL start[c]up 2.0 Round 2 : C. Elections

これは割と面白かった。
http://codeforces.com/contest/458/problem/C

問題

N人の人がいる町で選挙を行う。
今各人がどの候補者に入れるつもりかがA[i]で与えられる。
ただ、それぞれS[i]のお金を与えれば寝返って自分に投票してくれることがわかっている。

選挙に当選するには、他の誰よりも得票数が多くなければならない。
0番の候補者が当選するのに必要な最小金額を答えよ。

解法

得票数xで当選するための金額は以下のように求めることができる。

• 既にx以上得票予定の候補者がいる場合、金額が安い順に寝返らせて(x-1)票にする。
• 上記処理でまだ自分がx票に達しない場合、まだ寝返ってないからで金額が安い順に寝返らせて自分をx票にする。

事前にソートをしておけば、上記処理はO(N)で出来る。
xに対して金額は下に凸になるので、三分探索などで解くことができる。
以下のコードでは、xを300単位で大ざっぱに探索して、その後細かく探索している。

int N;
vector<int> V[100001];
vector<int> VV;

ll dodo(int num) {
	ll tot=0;
	int i,j,left;
	int ng[10001];
	left=num-V[0].size();
	ZERO(ng);
	for(i=1;i<=100000;i++) {
		FOR(j,(int)V[i].size()-(num-1)) tot+=V[i][j], left--, ng[V[i][j]]++;
	}
	FOR(i,VV.size()) {
		if(left<=0) break;
		if(ng[VV[i]]) ng[VV[i]]--;
		else left--, tot+=VV[i];
	}
	
	return tot;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x>>y, V[x].push_back(y);
	for(i=1;i<=100000;i++) {
		sort(V[i].begin(),V[i].end());
		ITR(it,V[i]) VV.push_back(*it);
	}
	sort(VV.begin(),VV.end());
	
	int mid=0;
	ll mi=1LL<<40;
	for(i=1;i<=N;i+=300) {
		ll ret=dodo(i);
		if(ret<mi) mi=ret,mid=i;
	}
	
	for(i=mid-300;i<=mid+300;i++) if(i>=1 && i<=N) mi=min(mi,dodo(i));
	cout << mi << endl;
	
}

まとめ

これは探索問題というのはすんなり思いつけた。