Codeforces #219 Div1. A. Counting Kangaroos is Fun

CF219に参加。とかく計算時間に泣かされた回。
A : hackの入力長制限に引っかかって本来認められる入力が認められず、数を絞ったらTLEしなかった。
B : 横着したコードを書いたらTLEした。
C : 計算量を落とすコードを知らず落としきれなかった。
結局本番はAのみ正解。
http://codeforces.com/contest/372/problem/A

問題

N匹のカンガルーのサイズS[i]が与えられる。
カンガルーは自分より倍以上大きなカンガルーのポケットに入ることができる。
ただし、1匹のポケットに2匹以上入ることはできず、またすでにポケットに他のカンガルーを入れているカンガルーは、他のポケットに入ることができない。

ポケットに入っていないカンガルーの数を最小化せよ。

解法

最初、入れ子状にカンガルーを入れるのもokと勘違いしてWAした。
それでもサンプルケース通っちゃうのよね。
他にも同じミスをした人がちらほらいたらしい。

S[i]をソートして、上位K匹のポケットに下位K匹が入るか、という判定をKを二分探索しながら行えばよい。

別解としては、どうせ入れ子がないなら、サイズが上半分のカンガルーに下半分のカンガルーを詰めていく、という手順でも良い。

int N;
int S[600000];

int okok(int r) {
	int i;
	if(2*r>N) return 0;
	FOR(i,r) if(S[N-1-i]<S[r-1-i]*2) return 0;
	return 1;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	
	int r=0;
	sort(S,S+N);
	
	l=0;r=10*N+1;
	FOR(i,30) {
		int p=(l+r)/2;
		if(okok(p)) l=p;
		else r=p;
	}
	l=max(0,l-3);
	while(okok(l)) l++;
	_P("%d\n",N-(l-1));
}

まとめ

相変わらず二分探索は１ずれるのが怖くて最後に調整してしまう。