ハル研究所プログラミングコンテスト2012

ハル研究所プログラミングコンテスト2012の参加記
結果は学生部門5位、総合6位でした。
工夫したこととか書いていきます。
・乱数の種を変えたりして実験したら最適解はトゲを踏んだり待機しないっぽいのでdist[x][y][トゲの周期][アイテム]で探索
・最初BFSしてたけどA*の方が速いのでそっちに切り替え
・ヒューリスティックはトゲを無視した最短路
・よく考えると行動した後の推定値の変動は+0,+1,+2のいずれかなのでヒープを使わず、バケットを4個用意して循環させて使い優先度付きDFSする
その他高速化の工夫
・とりあえずループ展開して条件判定を減らす
・距離テーブルのサイズが大きいので最初に全て初期化した後は更新箇所を記録しておきそこだけ初期化する
・配列が大きくなるならintではなくcharで宣言してキャッシュに載りやすくする（2倍ほど速くなって驚愕）
・hoge[24][24]とかはhoge[24][32]とするとコンパイラがシフトで最適化してくれる
・距離テーブルは一次元配列として宣言する
こんな感じでマクロを使ってアクセスしメモリを詰めて使用する

uchar dist[Constant::FIELD_WIDTH_MAX*Constant::FIELD_HEIGHT_MAX*Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1)];
#define DIST(x,y,c,p) (dist[(((((x)*height+(y))*Constant::SPINE_TURN_CYCLE)+(c))*(Constant::SPINE_TURN_PAUSE+1))+(p)])

上下左右に移動する場合その中心座標のアドレスを計算しておくと移動先のアドレスは定数オフセットでアクセスできるので演算命令を減らせる。
オフセットは探索前に計算

const int down = Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1);
const int right = height*Constant::SPINE_TURN_CYCLE*(Constant::SPINE_TURN_PAUSE+1);

中心座標のアドレスを計算したら上下左右のアドレスはオフセットで計算できる

p[-down]
p[-right]
p[right]
p[down]