■ [TCO][MM]TCO Marathon Round2 
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14273&pm=10989
300人→100人、ここを抜けるとTシャツ
問題概要
2次元セルオートマトンの遷移規則と初期状態が与えられる。
与えられた初期状態のN箇所以下を反転させて、Kターン後の生きているセルの数を最大化せよ。
自明解＋α
まずは、入力をそのまま返してみたらどのくらいのスコアになるのか手元でやってみた→seed1〜200で34.3pt
standingsの35.16ptで並んでる人たちはこの解を提出したんでしょうね
Kが最大20もあるので、解析的に配置していくのは難しそう
とりあえず焼きなませるのでやってみた。近傍の取り方は、どこか1マスを反転させるかどうかの切り替えで
提出1回目→40.69pt（実はこれには非常に単純なミスがあった。修正すると44ptくらい）
【余談】
焼きなましだとランダム性があるので、何度も同じケースをテストして「お、今回はけっこう伸びた」みたいに無駄に時間を使うことがあった
それを回避するため、今回は乱数の種は固定にしてみた。おかげでテスト中に繰り返し同じケースを動かすことは減った
けれどもオーバーフィッティングになっていないか少々不安…
いつもの高速化
最初のコードでは、Kステップ後の生き残り個数を調べるのに単純に盤面全体をシミュレーションしていてとても遅かった
大きいサイズのテストケースだと、焼きなましのイテレーションが200回くらいしかできないという残念な事態
というわけで、前回のシミュレーション結果を取っておいて差分だけを計算するようにした。これで数倍〜数百倍高速化された
まあいつもやってるようなこと
提出2回目→46.63pt
いろいろ改善
みるみるうちに順位が下がる…さすがTCO。このままでは通過も危ない
改善の余地はいろいろありそうなので頑張る
シミュレーションの計算範囲を限定
1点を反転させたとき、影響が及ぶのはその点を中心とする(2K+1)*(2K+1)の四角形の範囲だけ。この領域を調べればよい
（というか、1点だけの変化という近傍を採用したのはこの高速化を可能にするため）
これは盤面が大きくてKが小さい場合には劇的に効く
本当は、変化させる点の0ステップ目を頂点として、ステップが進むにつれて広がっていく四角錐の範囲だけ調べれば良くて、調べる量がさらに1/3になり得る
が、ちょっと書こうとしてみたところ、境界の取り扱いなどで複雑になってしまって、あまり高速化にはならなさそうだったので採用せず
剰余演算を削減
盤面の上下左右がつながっているため、ナイーブな実装では、隣接したセルの座標を指定するのに剰余演算が出てくる （field[(r+dr[i])%R][(c+dc[i])%C] みたいな）
ループ内部で何度も同じ剰余演算が行われるのは避けたいので、前計算して配列に入れておいてアクセスするようにした
1割くらい速くなった
ループ最内での条件分岐削減
ナイーブな実装では、シミュレーションのステップを進めていくとき、各セルに対して以下のような条件分岐が入る
if (rule[count] == '+') { ... } else if (rule[count] == '-') { ... } else if ...
ruleは入力をそのままcharで持っておくのではなくて、次のような配列にしておいて、インデックスアクセス一発で次のセルがどの状態になるか取得できるようにした
rule = {false, false, // ruleが'-'
true, true, // ruleが'+'
false, true, // ruleが'='
true, false, // ruleが'X'
};
//1step前： ↑生きてた ↑死んでた
これも1割くらい速くなった
ループ展開
あるセルがliveになったとき、その周囲8マスに対して「周囲のliveなセルの個数」カウントをインクリメントする
このとき、普通に書くと次のようになる
for (int i = 0; i < 8; ++i) { count[r+dr[i]][c+dc[i]]++; }
これを、ループを展開してベタに書くと速くなる
count[r+dr[0]][c+dc[0]]++;
count[r+dr[1]][c+dc[1]]++;
...
count[r+dr[7]][c+dc[7]]++;
一番のボトルネック箇所なので、これだけでも5%くらい高速化した
前回の結果と変化がなくなったら以降のシミュレーションは省略
ケースによっては速くなった気がする
局所解からの脱出
基本的にはたくさん反転させた方がいい結果になるので、N個全部使った場合に状態が張り付いてしまう恐れがある
これを引っぺがすため、反転箇所をN個全部使っている状態からN-1個しか使っていない状態への遷移は他のよりも起きやすいようにした
たぶんけっこう効いてる
これらの改善が入った提出5回目→47.47pt
あまり上がらない…厳しい…
近傍の取り方の改善
1点調べて状態遷移、とするのではなくて、反転箇所の候補をランダムに5点調べて一番良かったところに遷移するようにしたらかなり効いた
提出6回目→49.29pt
他に、タブーサーチ的な仕組みを入れてみたり、どのくらいの割合で遷移が起きているかに応じて温度を動的に調節してみたりしてみたけど効果はなかった
盤面のbit化
制限時間を倍にしてテストしてみると0.5ptほど上がることを確認。アルゴリズム的なアイディアが尽きてきたこともあり、ラスト2,3日は高速化に絞って改善した
盤面を boolean[R][C]（生死の状態）と int[R][C]（周囲にある生きているセルの数）で持っていたのを、
生死をbitで表して long[R][C>62?2:1] だけで持つようにしてみた。これで盤面のコピーがかなり軽くなるはず
62が閾値なのは盤面の左右が繋がっているのをうまく扱うための事情
シミュレーションは頑張ってビット演算をごにょごにょにょごにょご…
ローカルではむしろ遅くなってがっくりしていたが、サーバーでテストするとケースによって倍くらい速くなっていた
Forumにも同じような話が出ていて、CPUのキャッシュサイズの問題らしい
最後の提出→49.65pt（暫定46位/254人）
最終結果と感想
【後で書く】
