Codeforces #188 Div1. B. Ants

これは本番何とか解けた問題。
http://codeforces.com/contest/317/problem/B

問題

初期状態で座標(0,0)にN匹のアリがいる。
時間1ごとに、ある座標に4匹以上のアリがいる場合、うち4匹のアリが上下左右の隣接マスに1匹ずつ動く。
アリの移動がなくなるまで上記処理を繰り返す。

この状態で座標が与えられたとき、そこにいるアリの数を答えよ。

解法

アリの移動をシミュレートすると、Nが最大値30000であっても、30000時間後、(-70,-70)-(70,70)の範囲に蟻が散らばることがわかる。
後はアリの数を答えればよい。

ただ、まじめに30000時間を上記座標でシミュレートするとTLEするので、第一象限だけでシミュレートして計算時間を1/4にした。

int N,T;
int A[2][71][71];
set<int> V[2];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N>>T;
	A[0][0][0]=N;
	FOR(i,30000) {
		int cur=i%2;
		int tar=1-cur;
		ZERO(A[tar]);
		FOR(x,70) FOR(y,70) {
			if(A[cur][y][x]>=4) {
				if(y>0) A[tar][y-1][x]++;
				if(y-1==0) A[tar][y-1][x]++;
				A[tar][y+1][x]++;
				
				if(x>0) A[tar][y][x-1]++;
				if(x-1==0) A[tar][y][x-1]++;
				A[tar][y][x+1]++;
				A[cur][y][x]-=4;
			}
			A[tar][y][x]+=A[cur][y][x];
		}
	}
	
	FOR(i,T) {
		x=abs(GETi());
		y=abs(GETi());
		if(x>70 || y>70) _P("%d\n",0);
		else _P("%d\n",A[0][y][x]);
	}
}

まとめ

頭でいろいろ考えるより、いったんシミュレートした方が楽という問題。
第1象限だけにするアイデアが先に思いついてよかった。