kmjp's blog

競技プログラミング参加記です

MemSQL start[c]up Round 1 : B. Stadium and Games

精度周りのツメが甘くて本番落とした問題。
http://codeforces.com/contest/325/problem/B

問題

Aチームで大会を開催するとき、試合回数は以下の手順で決まる。

  • Aが偶数の場合、2チームずつペアにして敗者が脱落する。すなわちA/2試合してA/2チームが脱落する。これをAが偶数の間繰り返す。
  • Aが奇数になったら、総当たり戦、すなわちA*(A-1)/2試合して勝者を決める。

ここで、総試合数Nが与えられたとき、試合数がNになるチーム数Aを列挙せよ。

解法

最初i回チーム数を半減して奇数になったとする。
この時、チーム数は奇数Xを用いてX*2^iチームである。
また、試合数はX*(X-1)/2 + X*(2^i-1)=Nなので、整理するとX^2 + (2^(i+1) - 3) + 2N=0となる。

各iについて上記方程式を解き、Xが奇数な整数となるものを選べばよい。
誤差が怖かったので、念のため得られた整数値で再度試合数をチェックしている。

ll N;
int okok(ll M) {
	ll res=0;
	while(M%2==0) {
		res+=M/2;
		M/=2;
	}
	res += M*(M-1)/2;
	return res==N;
}

void solve() {
	int f,r,i,j,k,l, x,y;
	vector<ll> res;
	cin>>N;

	FOR(i,61) {
		ll B=(1LL<<(1+i)) - 3;
		ll C=2*N;
		if(B>C) break;
		double D = sqrt(B*(double)B+8*(double)N+1e-9);
		if(D-(ll)D <= 1e-9) {
			ll B2 = (ll)D-B;
			if(B2%2==0 && B2%4!=0 && okok((B2/2)<<i)) res.push_back((B2/2)<<i);
		}
	}
	sort(res.begin(),res.end());
	res.erase(unique(res.begin(),res.end()),res.end());

	if(res.empty()) _P("-1\n");
	else FOR(i,res.size()) cout << res[i] << endl;
}

まとめ

誤差回りで失点するのはもったいないなぁ…。