ハル研究所プログラミングコンテスト2012 工夫した点とか

方針とか

10^6回してみたけど、針を踏まない、開始地点以外で待機しなくてもゴールにたどり着けたので、「針を踏まない方向への移動」 + 「アイテム使用」のみを考えるA*で解いた
ゴールまでの距離をBFSで計算して、ヒュースティック値にする
memo化する際に、[ゲームのターン数][縦][横][アイテムの残り時間] の配列で保存していたが、

- ゲームのマス目は210でループするので、ターン数が210を超えた時は、 -210してあげても問題ない
- [アイテムの残り時間][縦][横][ゲームのターン数]の方が、キャッシュに乗りやすくて早かった

ヒュースティック値と、現在の超過コストをkeyとして、priority_queueに入れて回す。

工夫(高速化)したところ

classで実装しているもののほとんどをinline関数に書き換える
int,shortを控えてcharにする(2倍は変わる)
関数の引数が4つくらいある場合は、引数をstructかclassにして、const &で渡した方が呼び出しが早くなる
charの変数を初期化する際、intにキャストして代入することで、初期化が4倍くらい早くなる

char _penalty[5 + 1][24][24][210];

void init(){
	for(int i = 0; i < 725760 / 4; i += 16){
((int*)_penalty)[i+15] = ((int*)_penalty)[i+14] = ... ((int*)_penalty)[i+0] = 0x70707070;
	}
}

現在いる場所のヒュースティック値と現在の超過コストを比較する際、shortに無理矢理キャストすることで比較演算の速度を上げる

priority_queue使ってたので比較演算の速度を上げると1.5倍くらい早くなった気がする
ただし、ビッグエンディアンなのでソースがローカルとサーバー側で変える必要がある。

こんな感じ

#define FORCE_SHORT(x) (((short *)(void *)&(x))[0])

//サーバと自分のPCではエンディアンが違うので、FORCE_SHORTでの比較が可能になるように変更しておく
struct Result{

#ifdef DEBUG
	char heu;
	char penalty;
#else
	char penalty;
	char heu;
#endif

	short item_time;
	short turn;

	Result(){}

	Result(short turn,short item_time,char penalty,char heu) 
		: turn(turn),item_time(item_time),penalty(penalty),heu(heu) {}
	short Point() const{ return _turnbouns - penalty + _nonStopBouns + 10; }

};

...

inline bool Greater(const Result& l,const Result& r) {
	return FORCE_SHORT(l) < FORCE_SHORT(r);
}

inline bool LessThan(const Result& l,const Result& r) {
	return FORCE_SHORT(l) >= FORCE_SHORT(r);
}

forループを展開して書く

よく

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
for(int i = 0 ; i < 4; i++){
    int nx = x + dx[i],ny = y + dy[i];
    call_any_functions();
}

みたいなことをするんですが、

Pos next_pos = cur_pos;
//左
next_pos.x -= 1
call_any_function();
//右
next_pos.x += 2
call_any_function();
//下
next_pos.x -= 1
next_pos.y -= 1
call_any_function();
//上
next_pos.y -= 1
call_any_function();

って要領で書くと早くなった

とりあえず思いつく限り書いてみました