TopCoder SRM 550 Div1 Medium CheckerExpansion

問題

無限に広いチェス盤がある。最初どのマスにも駒は置かれていない。
左上を(0, 0)とする。以下t回以下の操作を繰り返す。

• 1回目は(0, 0)にAを置く
• 次からはB, Aと交互に置く
• (x - 2, y)と(x - 1, y - 1)の2マスのうち、どちらか一方のみに今置こうとしている駒でない駒があった場合、(x, y)に駒を置く

操作を繰り返した後のチェス盤の、
(x0, y0)から幅w高さhの部分を出力せよ。

制約条件

t≦10^12
x0, y0≦10^12
h, w≦50

方針

A.B.A.B.A.B.A.B.A.B.A.B.A.B.A.
.B...B...B...B...B...B...B...B
..A.B.....A.B.....A.B.....A.B.
...B.......B.......B.......B..
....A.B.A.B.........A.B.A.B...
.....B...B...........B...B....
......A.B.............A.B.....
.......B...............B......
........A.B.A.B.A.B.A.B.......
.........B...B...B...B........
..........A.B.....A.B.........
...........B.......B..........
............A.B.A.B...........
.............B...B............
..............A.B.............
...............B..............
................A.B.A.B.A.....
.................B...B........
..................A.B.........
...................B..........

実験してみると、上のように駒が置かれることがわかる。
t回後には、x + y == 2 * tの駒が置かれるので、x + y≦2*tの部分だけ、
どの駒があるかを考えればよい。

どうみてもフラクタルなので、再帰してフラクタルのどの部分に(x, y)があるかを調べる。（苦手）

ソースコード

char calc(ll y, ll x){
	if(x < y) return '.';
	
	ll h = 2, w = 4, level = 1;
	while(y >= h || x >= w){
		h *= 2;
		w *= 2;
		level++;
	}
	while(level > 1){
		h /= 2;
		w /= 2;
		level--;
		
		if(y < h) x = x % w;
		else{
			y -= h;
			x -= h;
		}
		
		if(x >= h && x + y > w - 2) return '.';
		if(x < h && x < y) return '.';
	}
	if(y == 0) return "A.B."[x];
	return ".B.."[x];
}

class CheckerExpansion {
	public:
	vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) {
		vector<string> ans(h, string(w, '.'));
		rep(i, h) rep(j, w){
			if(y0 + i + x0 + j < 2 * t) ans[h - 1 - i][j] = calc(y0 + i, x0 + j);
		}
		return ans;
	}
};