Codeforces #188 Div2 D "Ants"

問題

http://codeforces.com/contest/318/problem/D

訳

方眼紙上に置いたある蟻は次のような習性がある。同じ(x, y)地点いる蟻達は４匹ずつでグループを作り、それぞれが(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程に収まるようだ。
なので、それらの範囲に限り、シミュレートしていく。
１回更新ごとに、140 * 140で１万を超えるが、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] );
        }
    }
}