Good Bye 2016 : D. New Year and Fireworks

そういえばあけましておめでとうございます。
http://codeforces.com/contest/750/problem/D

問題

無限に広がる二次元のグリッド上で絵を描く。
絵のパラメータはN要素の数列A[i]で与えられる。

パラメータをもとに、以下のように絵を描く。
あるマスを現在位置とし、そこから始め、A[0]だけ上方向に升目を辿り通過したマスに色を塗る。
すると、そこから45度左に回転した向きと、45度右に回転した向きそれぞれにA[1]マス移動しながら色を塗る。

同様に、A[i]マス移動しては45度左右に回転した２方向に分岐して、それぞれA[i+1]マス分岐する…を繰り返す。
全体で塗ったマスはいくつか。

解法

愚直にシミュレートするとO(2^N)回程度分岐するのでTLEする。
ただ、考えてみると現在位置は初期位置から高々O(sum(A)^2)程度の範囲のマスしか動かない。
よって、同じ位置、同じ向きである状態をメモ化し、無駄に何度も繰り返さないことで処理を軽量化できる。

int N;
int T[55];
int dirx[9]={0,-1,-1,-1,0,1,1,1,0};
int diry[9]={1,1,0,-1,-1,-1,0,1,1};
int did[400][400];
int from[400][400];
int to[400][400];


void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N;
	from[200][200]=1;
	FOR(i,N) {
		ZERO(to);
		cin>>r;
		if(i==0) r--;
		FOR(x,400) FOR(y,400) if(from[x][y]) {
			did[x][y]=1;
			FOR(z,8) if(from[x][y]&(1<<z)) {
				int tx=x,ty=y;
				FOR(j,r) {
					tx += dirx[z];
					ty += diry[z];
					did[tx][ty]=1;
				}
				to[tx][ty] |= (1<<((z+1)%8));
				to[tx][ty] |= (1<<((z+7)%8));
			}
		}
		swap(from,to);
	}
	int ret=0;
	FOR(x,400) FOR(y,400) ret+=did[x][y];
	cout<<ret<<endl;
}

まとめ

これはすんなり思いつけてよかった。