Golden Week Contest 2015 B アリ巣
問題
方針
ラングトンの蟻と言うらしい。
$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);
// }
}