TopCoder SRM 550 Div1 Medium CheckerExpansion

これも本番には解けず。
http://community.topcoder.com/stat?c=problem_statement&pm=11995

問題

無限大に広い2次元グリッドがある。
以下のルールで'A'か'B'の文字を各セルにおいていく。

初手で座標(0,0)に文字'A'を置く。
以後、1手ごとに各セルについて以下の処理を行う。

• 座標(x-1,y-1)に文字があり、(x-2,y)が空なら、(x,y)に(x-1,y-1)と逆の文字を置く。
• 座標(x-2,y)に文字があり、(x-1,y-1)が空なら、(x,y)に(x-2,y)と逆の文字を置く。

ここで手数Tが与えられ、グリッド上の矩形領域が指定される。
T手後の矩形領域の状態を示せ。

解法

Editorialを参照。

まずTを無限に大きいと仮定すると、この図形は2^x手ごとに再帰的な形状を取る。
よって再帰的な図形を逆にたどり、最終的にAとBのどちらが入っているか調べればよい。

Tについては(x,y)に文字が入るのは(x+y)/2手後なので、これで判断することができる。

class CheckerExpansion {
	public:
	
	char cha(ll t,ll X,ll Y) {
		if(t==0) return '.';
		if(t==1) return (X==0&&Y==0)?'A':'.';
		if(t==2) {
			if(X==0&&Y==0) return 'A';
			if(X==1&&Y==1) return 'B';
			if(X==2&&Y==0) return 'B';
			return '.';
		}
		
		ll mp=1;
		while(mp*2<t) mp*=2;
		
		if(X<2*mp&&Y<mp) return cha(mp,X,Y);
		if(X<4*mp&&Y<mp) return cha(t-mp,X-2*mp,Y);
		if(X<3*mp&&Y<2*mp) return cha(t-mp,X-mp,Y-mp);
		return '.';
	}
	
	vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) {
		vector<string> res;
		int x,y;
		FOR(y,h) {
			res.push_back("");
			FOR(x,w) res.back().push_back(cha(t,x0+x,y0+h-1-y));
		}
		return res;
	}
}

まとめ

これが再帰的な形状になる、ということが本番思い浮かばなかった。