TopCoder SRM 732 Div1 Medium BrownieGame

ええ…。
https://community.topcoder.com/stat?c=problem_statement&pm=14841

問題

グリッド状になったブラウニーがいくつかある。
それぞれの縦・横のマス数が与えられる。

これらを用いてAB２人でゲームを行う。
Aはどれか１つブラウニーを選択し、マス目にそって横に割る（横にしか割れない）。
Bは同様に縦に割る。
自分の手番で割れるブラウニーがない場合負けとなる。

Bが必勝となるには、Bしか割れない縦2*横1のブラウニーを何個余分に準備すればよいか。

解法

どうも既出のようだ。
ブラウニーの形状に対し、どちらが何手余分に割ることができるかはすでに先行研究があるらしく、Codeforcesで指摘されている。
http://codeforces.com/blog/entry/58590?#comment-422462

ここから、各ブラウニーに対し後手が何手余裕があるかその和を求め、余裕がない分は2*1のブラウニーを追加すればよい。

class BrownieGame {
	public:
	
	int hoge(int R,int C) {
		if(R==C) return 0;
		if(R>C) return -hoge(C,R);
		int sum=0;
		for(int step=1;;step<<=1) {
			sum+=step;
			if(R<=sum) return C/step-1;
		}
		return 0;
		
	}
	
	vector <int> HowToCheat(int n, vector <int> r, vector <int> c) {
		int ret=0;
		int i;
		FOR(i,n) ret+=hoge(r[i],c[i]);
		return {max(0,ret),max(0,ret+1)};
		
	}
}

まとめ

Hardも同じ出典っぽい？