Golden Week Contest 2015 B アリ巣

2015/05/05 (Tue) AtCoder 周期性 OEIS

問題

問題文

方針

ラングトンの蟻と言うらしい。 $10000$ あたり(!)から長さ $104$ (!!)の周期が現れる。下のコードのdirの数列をOEISにかけたらヒットしたので解けた。 (A255938)

実装

いろいろ試したのでとても汚い。

int h = 1000;
int w = 1000;
bool s[1000][1000];
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

signed main(){
    int N;
    cin >> N;
    memset(s,0,sizeof(s));
 
    int x = w/2;
    int y = h/2;
    int dir = 0;
    vi hist;
    vi pat;
    rep(i,20000){
        if(s[y][x]){
            dir++;
        } else {
            dir--;
        }
        s[y][x] ^= 1;
        dir &= 3;
        x += dx[dir&3];
        y += dy[dir&3];
        hist.pb(s[y][x]);
    }
    rep(i,104){
        if(s[y][x]){
            dir++;
        } else {
            dir--;
        }
        s[y][x] ^= 1;
        dir &= 3;
        x += dx[dir&3];
        y += dy[dir&3];
        pat.pb(s[y][x]);
    }
 
    if(N < hist.size()){
        cout << hist[N-1] << endl;
    } else {
        assert(N >= 20000);
        N--;
        N -= hist.size();
        N %= pat.size();
        cout << pat[N] << endl;
    }
 
    // {
    //     vector<int> recent(hist.rbegin(), hist.rbegin()+100);
    //     reverse(all(recent));
    //     dump(recent);
    // }
    // {
    //     vector<int> recentc(histc.rbegin(), histc.rbegin()+1000);
    //     reverse(all(recentc));
    //     dump(recentc);
    // }
}