TopCoderOpen 2019 Round2A : Medium Byes

書き方色々ありそう。
https://community.topcoder.com/stat?c=problem_statement&pm=15471

問題

L人でトーナメントの勝ち抜き戦を行うことを考える。

• 残った人数が偶数であれば1回戦でL/2人が勝ち残る。
• 残った人数が奇数であれば、1人はシード扱いとなり1回戦で(L+1)/2人が勝ち残る。

整数L,Bが与えられる。
L人以上のトーナメントのうち、シードがB回生じるような最少人数は何人か。

解法

試合回数Mを決め打ちすることを考える。
決勝以外毎回シードが発生するとすると、M試合行う最少人数は(2^(M-1)+1)である。
1回戦、2回戦…でシードが無い状態にするには、参加者数が1,2,4,...人多ければ良いことになる。

よって、1,2,4,...のうち(M-1-B)個選択し、その和をSとすると、(2^(M-1)+1)+S≧Lとなる最小のSを求めればよい。
これは大きい順に貪欲に選択する・しないを選べばよい。
選ばなくても和と選択個数が条件を満たすなら選ばないし、そうでなければ選ぶ。

L=1,B=0の場合だけ注意。

class Byes {
	public:
	
	long long getNumberOfPlayers(long long L, int B) {
		
		if(L==1 && B==0) return 1;
		
		ll cand=1LL<<62;
		int i;
		for(int step=B+1;step<=61;step++) {
			ll tot=2;
			FOR(i,step-1) tot=tot*2-1;
			ll dif=L-tot;
			
			int lef=step-1-B;
			
			for(i=step-2;i>=0&&lef>=0;i--) {
				if(lef==i+1 || ((((1LL<<lef)-1)<<(i-lef))<dif)) {
					lef--;
					tot+=1LL<<i;
					dif-=1LL<<i;
				}
			}
			if(lef==0 && dif<=0) cand=min(cand,tot);
		}
		
		return cand;
		
		
	}
}

まとめ

普通1回戦のbyeの個数を調整して2のべき乗人数が残るようにするよね…。