Codeforces #188 Div2 D "Ants"
問題
http://codeforces.com/contest/318/problem/D
訳
方眼紙上に置いたある蟻は次のような習性がある。同じ(x, y)地点いる蟻達は4匹ずつでグループを作り、それぞれが(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)へと移動する。余った蟻は(x, y)に留まる。グループが作れなくなった時点で、蟻たちの動きは完全に止まる。
(0, 0)にn匹の蟻を置く。そして蟻の動きが完全に止まるまで待つ。それから(qx, qy)地点にいる蟻の数は?というクエリがm回くるので、それぞれを出力せよ。
制約
1 <= n <= 30000
1 <= m <= 50000
考えた事
どうも蟻の動く範囲はx, yが-70~70程に収まるようだ。
なので、それらの範囲に限り、シミュレートしていく。
1回更新ごとに、140 * 140で1万を超えるが、n=30000でも問題なかった。割と早く蟻たちの動きは止まってしまうらしい。
実験ばっか。数学的にはまったく理解してません!
ソースコード
const int LEN = 131; int ants[2][LEN][LEN]; int main() { int n, t; cin >> n >> t; // 蟻の動きをシミュレート memset( ants, 0, sizeof(ants) ); ants[0][LEN/2][LEN/2] = n; int d = 1; int s = 0; while( true ){ bool update = false; memset( ants[d], 0, sizeof(ants[d]) ); for( int y = 0; y < LEN; y++ ){ for( int x = 0; x < LEN; x++ ){ if( ants[s][y][x] >= 4 ){ update = true; int add = ants[s][y][x] / 4; int rem = ants[s][y][x] % 4; ants[d][y][x+1] += add; ants[d][y][x-1] += add; ants[d][y+1][x] += add; ants[d][y-1][x] += add; ants[d][y][x] += rem; }else{ ants[d][y][x] += ants[s][y][x]; } } } if( !update ) break; swap( s, d ); } // クエリに答える int MAX_ABS = LEN / 2; for( int i = 0; i < t; i++ ){ int x, y; cin >> x >> y; if( abs(x) > MAX_ABS || abs(y) > MAX_ABS ){ printf( "%d\n", 0 ); }else{ x += LEN / 2; y += LEN / 2; printf( "%d\n", ants[s][y][x] ); } } }