Codeforces #207 Div1. C. Compartments

さてC。こちらも割と早めに回答が思いついたがツメが甘くwrong answer…。
http://codeforces.com/contest/356/problem/C

問題

N個の部屋に学生が0～4人いる。
学生を移動させて、学生がいる部屋はすべて3人以上となるようにしたい。
学生の移動数を最小化せよ。

解法

まず、総学生数が1,2,5の時は3・4の和で表せないので答えはなし。
総学生数をSとするとき、3人部屋数をP3、4人部屋数をP4とすると以下の条件を満たすP3・P4がおおむねS/12通りぐらい考えられる。

• P3 + P4 <= N
• 3*P3 + 4*P4 == S

上記式を満たすP3・P4について、その部屋数に学生数をおしこめる場合に移動する学生数を数えればよい。
P3・P4のパターンはO(S)でこれは結局O(N)だし、移動する学生数のカウントはO(1)でできるので全体でO(N)で処理できる。

学生のおしこめ方は、初期状態で人数が多い上位P4個の部屋を4人部屋となるようにし、次の(P4+1)～(P4+P3)番目に学生の多い部屋を3人部屋となるようにすれば、過不足を埋める移動人数分がO(1)で求められる。

int N;
int A[5];

int dodo(int p4,int p3,int ma) {
	int B[5];
	int i,x,r=0;
	FOR(i,5) B[i]=A[i];
	while(p4) {
		if(r>=ma) return r;
		if(B[4]) {
			i=min(B[4],p4);
			B[4]-=i,p4-=i;
			continue;
		}
		if(B[3]) {
			i=min(B[3],p4);
			r+=i;
			B[3]-=i,p4-=i;
			continue;
		}
		if(B[2]) {
			i=min(B[2],p4);
			r+=2*i;
			B[2]-=i,p4-=i;
			continue;
		}
		if(B[1]) {
			i=min(B[1],p4);
			r+=3*i;
			B[1]-=i,p4-=i;
			continue;
		}
	}
	while(p3) {
		if(r>=ma) return r;
		if(B[4]) {
			i=min(B[4],p3);
			B[4]-=i,p3-=i;
			continue;
		}
		if(B[3]) {
			i=min(B[3],p3);
			B[3]-=i,p3-=i;
			continue;
		}
		if(B[2]) {
			i=min(B[2],p3);
			r+=i;
			B[2]-=i,p3-=i;
			continue;
		}
		if(B[1]) {
			i=min(B[1],p3);
			r+=2*i;
			B[1]-=i,p3-=i;
			continue;
		}
	}
	return r;
	
}

void solve() {
	int f,i,j,k,l,r, x,y;
	
	cin>>N;
	FOR(i,N) A[GETi()]++;
	int tot=A[1]+A[2]*2+A[3]*3+A[4]*4;
	if(tot<3 || tot==5) return _P("-1\n");
	
	int ma=1<<30;
	FOR(i,5) if((tot-i*3)%4==0) break;
	for(;i<=min(N+1,tot/3+1);i+=4) {
		x=(tot-i*3)/4;
		if(x<0 || i+x>N) continue;
		ma=min(ma,dodo(x,i,ma));
	}
	cout << ma << endl;
}

まとめ

せっかく久々にA,B,C解答できるチャンスだったのに、BもCもレートも落としてもったいない…。