HAL研究所プログラミングコンテスト2008 †
明日，コードが公開されちゃうので，こっちでも公開しておきます．
コンパイラの最適化が信用できなかったので，非常に長くて，非常に読みにくいコードですが，興味のある方はどうぞ．
gccな方は
#define inline // profile用
を消したほうが速いです．
/* cross word
Auther:Safii
HAL研究所プログラミングコンテスト2007用
-データ構造
変則双方向リストで，未使用の文字列と空いている空白の管理をしている
nextは次のノードのアドレスだが，parent(prevだよなぁ．．．)
は前のノードのメンバnextのアドレスになっている．
offsetの計算が省ける分速い．
-アルゴリズム
置く場所が確定している文字列は埋める(fast solve)
残った空白はscoreの高い物から深さ優先でがんばる．
scoreは空白同士の交差の数．
408374番目?の問題(階段状の空白がある)が遅いが
複雑な問題を高速に解く為に複雑な前処理をすると
簡単な問題でそのコストが無駄になる．今回位の規模の問題であれば，
シンプルなアルゴリズムが有利だったようです．
--文字列が置けるかどうかの判定
すでに置かれている文字と一致しない部分があればNG
また，nthChar[len][N][char]に
長さlenでN番目の文字がcharである文字列の数が入っている．
これとspaceAt[dir^1][y][x]から，直交する空白の長さlengthと
何番目で交差しているか(pos)を調べる．
で，nthChar[length][pos][ch]が0なら，そこに文字列を置けない事が
分かるのでNG
-枝狩
置ける文字列が一つも存在しない空白があったら即やめる．
-チューニング
ほとんどのC99の機能は使えないみたいですが，inlineが使えたので楽が出来た．
必ず展開して欲しい部分はマクロで．
ほぼ全ての関数は，縦と横方向それぞれ専用の関数を用意しています．(H,V
パイプラインを気にしたコーディングで10万点以上スコアが伸びた気がします．
過去のプロコンのページを，WebArchiveで読み漁って参考にしました^^;
分岐の2,3命令前にレジスタの値を更新するのは，とても効果がありました．
ただし，bdnz系の命令が使えそうな場合は，そっちの方が速いようです．
最後の一時間で，Spaceにメンバoffsetを追加しました．
cell[y][x] -> cell[0][offset]にできるので，掛け算の回数が減る気がします．
1000点位伸ばしたところでタイムアップでした．
-関数名のsuffix
H:横方向 V:縦方向に特化した物
-感想
サークルの後輩に誘われて参加しました．初めは後輩には負けないように，
ぐらいの気持ちで始めたのですが，気が付いたら夢中になっていました．
最後までシンプルなアルゴリズムで勝負したので，ずっと他の上位の方の
アルゴリズムが気になっていました．早くコードが読みたいです．
問題は簡単だったので，気軽に参加できてとても良かったです．
後半のチューニング対決はとにかく疲れました．
MAX_SIZEがもう少し大きいと，アルゴリズム勝負がもっと続いた気がします．
899回もsubmitしたのに，総合１位が取れなかったのが悔しいです．次回がんばります．
それと，ishimuraさんが最後に8000点更新したアイデアが気になります
とても楽しかったです．運営者，参加者の皆様お疲れ様でした．
-来年の僕へ
他の人のスコアを気にして，早い段階からチューニングやxxxxHVの様な
コーディングをしてると，後半が大変ですよ．
*/
#include "answer.h"
// スコアに影響はなかったけれど，キャッシュに乗りやすいかなと
#define MAX_STR_NUM 64 //(((MAX_SIZE+1) / 3) * MAX_SIZE * 2)
#ifdef _MSC_VER
#define inline __inline
#endif
#ifdef __GNUC__
#define inline // profile用
#endif
typedef struct Board Board;
// [len][nth][char]
// 長さlenでnth番目の文字がcharな文字列は何個ありますよ
// len==0はありえないので，ダミーとして使う
int nthChar[MAX_SIZE+1][MAX_SIZE]['z'+1]={{{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}}; //oops
// addr+offsetの計算を省く為にboardの中身を移しておく
int boardSize;
int stringNum;
char(*cell)[MAX_SIZE];
char(*boardStr)[MAX_SIZE+1];
// 残りの空白をlistで管理
typedef struct SPACE{
struct SPACE*next; // 次のノード
struct SPACE**parent; // 前のノードのnextのアドレス
int x;
int y;
int offset; // x + y*MAX_SIZE
int len;
int dir; // 0:縦 1:横
int score; // 優先度
int*nth[MAX_SIZE];
}Space;
// x, yのマスに文字が置かれたら1，縦横両方置くと2
int putCount[MAX_SIZE][MAX_SIZE];
// [0]は使わない．これは，makeSpaceList関数の用なループでアクセスする為
Space spaces[MAX_STR_NUM];
Space*spaceAt[2][MAX_SIZE][MAX_SIZE];
Space*spaceTop;
Space dummy={0, 0, MAX_SIZE, MAX_SIZE};
int position[2][MAX_SIZE][MAX_SIZE];
// なぜか速くなる．spaceAtで同じ事をしても速くならない(謎
int(*position0)[MAX_SIZE]=position[0];
int(*position1)[MAX_SIZE]=position[1];
// まだ置いていない文字列をlistで管理
typedef struct STRING{
struct STRING*next;
struct STRING**parent;
char*string;
}String;
// heap
String strings[MAX_STR_NUM];
// 長さnの文字列がn番目に入っている
String*stringTop[MAX_SIZE+1];
// strを走査して，nthCharを計算
inline void calcNthChar(const char*const str, const int len)
{
unsigned int j=len-1;
do
{
nthChar[len][j][(int)str[j]]++;
}while(--j);
nthChar[len][j][(int)str[j]]++;
}
// 文字列の情報を集めたり
inline void initStrings()
{
const int num=stringNum;
int i=0;
int len=2;
String**pNext=&stringTop[len];
String*next;
char*str, ch;
do
{
str=boardStr[i];
ch=str[len];
next=&strings[i++];
next->string=str;
// 与えられる文字列は長さ順にソートされているので
// 前回と長さが同じか調べてからstrlenをすれば良い
// str[len]==0なら前回と長さは一緒
if(ch)
{
*pNext=0;
do
{
len++;
}while(str[len]);
pNext=&stringTop[len];
}
next->parent=pNext;
*pNext=next;
pNext=&next->next;
calcNthChar(str, len);
}while(i<num);
*pNext=0;
}
// spaceにstringを置く
inline void putStringH(const Space*const space, const String*const string)
{
// int x=space->x;
// const int y=space->y;
int offset=space->offset;
const int len=space->len;
const char*const str=string->string;
int i=0;
String*pstr=string->next;
Space*pspc=space->next;
char ch;
// 一文字ずつ置いていく
do
{
ch=str[i];
putCount[0][offset]++;
nthChar[len][i][(int)ch]--; // nthCharの更新
i++;
cell[0][offset++]=ch;
}while(i<len);
// string->used=1;
*string->parent=pstr;
*space->parent=pspc;
if(pstr)
pstr->parent=string->parent;
if(pspc)
pspc->parent=space->parent;
}
inline void putStringV(const Space*const space, const String*const string)
{
//const int x=space->x;
//int y=space->y;
int offset=space->offset;
const int len=space->len;
const char*const str=string->string;
int i=0;
String*pstr=string->next;
Space*pspc=space->next;
char ch;
do
{
ch=str[i];
putCount[0][offset]++;
nthChar[len][i][(int)ch]--;
i++;
cell[0][offset]=ch;
offset+=MAX_SIZE;
}while(i<len);
*string->parent=pstr;
*space->parent=pspc;
if(pstr)
pstr->parent=string->parent;
if(pspc)
pspc->parent=space->parent;
}
#define putString(space,string)\
(space->dir?putStringH(space,string):putStringV(space,string))
// 文字列を戻す
inline void backStringH(Space*const space, String*const string)
{
// int x=space->x;
// const int y=space->y;
int offset=space->offset;
const int len=space->len;
const char*const str=string->string;
Space*pspc;
String*pstr;
int i=0;
*string->parent=string;
pstr=string->next;
*space->parent=space;
pspc=space->next;
// 戻すループ
do
{
nthChar[len][i][(int)str[i]]++; // nthCharの更新
i++;
// x,yに文字が置かれた回数を減らす．
// 0ならcellから文字をはがす
if(--putCount[0][offset]==0)
cell[0][offset]=WHITE;
offset++;
}while(i<len);
if(pstr)
pstr->parent=&string->next;
if(pspc)
pspc->parent=&space->next;
}
inline void backStringV(Space*const space, String*const string)
{
// const int x=space->x;
// int y=space->y;
int offset=space->offset;
const int len=space->len;
const char*const str=string->string;
Space*pspc;
String*pstr;
int i=0;
*string->parent=string;
pstr=string->next;
*space->parent=space;
pspc=space->next;
do
{
nthChar[len][i][(int)str[i]]++;
i++;
if(--putCount[0][offset]==0)
cell[0][offset]=WHITE;
offset+=MAX_SIZE;
}while(i<len);
if(pstr)
pstr->parent=&string->next;
if(pspc)
pspc->parent=&space->next;
}
#define backString(space,string)\
(space->dir?backStringH(space,string):backStringV(space,string))
#define getNthChar(len, n, ch) nthChar[len][n][(int)(ch)]
#define getCharLH(x,y)\
(x<0?BLACK:cell[y][x])
#define getCharLV(x,y)\
(y<0?BLACK:cell[y][x])
#define getCharL(dir,x,dx,y,dy)\
(dir?getCharLH(x-dx,y):getCharLV(x,y-dy))
#define getCharRH(x,y,size)\
(x==size\
?BLACK:cell[y][x])
#define getCharRV(x,y,size)\
(y==size\
?BLACK:cell[y][x])
#define getCharR(dir,x,dx,y,dy,size)\
(dir?getCharRH(x+dx,y,size):getCharRV(x,y+dy,size))
// スペースのlistにspaceを追加
// scoreで降順にソート(insertion sort)
inline void insert(Space*const space)
{
const int myWidth=space->score;
Space**s=&spaceTop;
// 挿す場所を探す
while(*s && (*s)->score>myWidth)
s=&(*s)->next;
space->next=*s;
*s=space;
space->parent=s;
if(space->next)
space->next->parent=&space->next;
}
inline void makeSpaceList()
{
int i=stringNum;
do
{
insert(&spaces[i]);
}while(--i);
}
inline void calcScoreH(Space*const space)
{
int x=space->x;
const int y=space->y;
int offset=space->offset;
int len=space->len;
int score=0;
int pos;
do
{
position0[0][offset]=pos=y-spaceAt[0][0][offset]->y;
len--;
if(pos>=0)
{
space->nth[x]=nthChar[spaceAt[0][0][offset]->len][pos];
score++;
}
else
space->nth[x]=nthChar[0][0];
x++;
offset++;
}while(len);
space->score=score;
}
inline void calcScoreV(Space*const space)
{
const int x=space->x;
int y=space->y;
int offset=space->offset;
int len=space->len;
int score=0;
int pos;
do
{
position1[0][offset]=pos=x-spaceAt[1][0][offset]->x;
len--;
if(pos>=0)
{
space->nth[y]=nthChar[spaceAt[1][0][offset]->len][pos];
score++;
}
else
space->nth[y]=nthChar[0][0];
y++;
offset+=MAX_SIZE;
}while(len);
space->score=score;
}
#define calcScore(s) ((s)->dir?calcScoreH(s):calcScoreV(s))
inline void calcScores()
{
int i=stringNum;
//scoreを求める
do
{
calcScore(&spaces[i]);
}while(--i);
}
// 右と下の範囲チェックを省いた版のfindAllSpaces
inline void fastFindAllSpaces()
{
#if __GNUC__
static int lastSize=0; // gccだと駄目
#else
static int lastSize=2; // 不安だけど0じゃなくても一応動く^^;
#endif
const int size=boardSize;
Space*s=spaces+1;
int y;
int x=0, X;
int prev;
Space**sp;
char ch;
// 右と下の縁にBLACKの壁を作ると，x,yの大きい側の範囲チェックが省ける
// 前回作った壁が使えるなら使う
if(lastSize!=size)
{
y=size;
for(; x<size; x++)
cell[y][x]=BLACK;
//x=size;
for(y=0; y<size; y++)
cell[y][x]=BLACK;
x=0;
lastSize=size;
}
y=0;
do
{
do
{
X=x++;
ch=cell[y][X];
putCount[y][X]=0;
if(ch==BLACK)
continue;
// dir:0
prev= y!=0?cell[y-1][X]:BLACK;//getCharLV(X, y-1);
sp=&spaceAt[0][y][X];
if(prev!=BLACK)
{
*sp=spaceAt[0][y-1][X];
(*sp)->len++;
}
else if(cell[y+1][X]==WHITE)
{
s->x=X;
s->y=y;
s->offset=X+y*MAX_SIZE;
s->dir=0;
s->len=1;
*sp=s;
s++;
}
else
*sp=&dummy;
// dir:1
prev= X!=0?cell[y][X-1]:BLACK;//getCharLH(X-1, y);
sp=&spaceAt[1][y][X];
if(prev!=BLACK)
{
*sp=spaceAt[1][y][X-1];
(*sp)->len++;
}
else if(cell[y][X+1]==WHITE)
{
s->x=X;
s->y=y;
s->offset=X+y*MAX_SIZE;
s->dir=1;
s->len=1;
*sp=s;
s++;
}
else
*sp=&dummy;
}while(x<size);
y++;
x=0;
}while(y<size);
}
// 空欄を探す
inline void findAllSpaces()
{
Space*s=spaces+1;
const int size=boardSize;
int X, x;
int y=0;
int dir;
int dx, dy;
int px, py;
int prev;
Space**sp;
char ch;
do
{
x=0;
do
{
X=x++;
ch=cell[y][X];
putCount[y][X]=0;
if(ch==BLACK)
continue;
for(dir=0; dir<2; dir++)
{
dx=dir; dy=dir^1;
px=X-dx; py=y-dy;
prev=dir?
(X?cell[y][px]:BLACK)
:(y?cell[py][X]:BLACK);
//getCharL(dir, X, dx, y, dy);
sp=&spaceAt[dir][y][X];
if(prev!=BLACK)
{
*sp=spaceAt[dir][py][px];
(*sp)->len++;
}
else if(getCharR(dir, X, dx, y, dy, size)==WHITE)
{
s->x=X;
s->y=y;
s->offset=X+y*MAX_SIZE;
s->dir=dir;
s->len=1;
*sp=s;
s++;
}
else
*sp=&dummy;
}//while(++dir<2);
}while(x<size);
}while(++y<size);
}
/* check
spaceにstringが置けるか調べる
すでに置かれている文字とnthCharを使って調べる
*/ [#ydab3c2d]
#define CHECK_H(space, string, error)\
{\
int x=space->x;\
int y=space->y;\
char cellch=cell[y][x];\
char*str=string->string;\
char ch=str[0];\
do\
{\
if(cellch!=WHITE)\
{\
if(cellch!=ch)\
{error;}/*別の文字が置かれてる*/\
}\
else if(space->nth[x][(int)ch]==0)/*他の文字の様子を伺う*/\
{error;}\
ch=*++str;\
cellch=cell[y][++x];\
}while(ch);\
}
#define CHECK_V(space, string, error)\
{\
int y=space->y;\
const int x=space->x;\
char cellch=cell[y][x];\
char*str=string->string;\
char ch=str[0];\
do\
{\
if(cellch!=WHITE)\
{\
if(cellch!=ch)\
{error;} /*別の文字が置かれてる*/\
}\
else if(space->nth[y][(int)ch]==0)/*他の文字の様子を伺う*/ \
{error;} \
ch=*++str;\
cellch=cell[++y][x];\
}while(ch);\
}
inline int checkH(const Space*const space, const String*const string)
{
int x=space->x;
int offset=space->offset;
char cellch=cell[0][offset];//space->y][x];
char*str=string->string;
char ch=str[0];
do
{
if(cellch!=WHITE)
{
if(cellch!=ch)
return 0; //別の文字が置かれてる
}
else if(space->nth[x][(int)ch]==0) // 他の文字の様子を伺う
return 0;
ch=*++str;
cellch=cell[0][++offset];
++x;
}while(ch);
return 1;
}
inline int checkV(const Space*const space, const String*const string)
{
int y=space->y;
// const int x=space->x;
int offset=space->offset;
char cellch=cell[0][offset];
char*str=string->string;
char ch=str[0];
do
{
if(cellch!=WHITE)
{
if(cellch!=ch)
return 0; //別の文字が置かれてる
}
else if(space->nth[y][(int)ch]==0) // 他の文字の様子を伺う
return 0;
ch=*++str;//[++i];
offset+=MAX_SIZE;
cellch=cell[0][offset];
y++;
}while(ch);
return 1;
}
static int tryPutString();
inline int tryPutAnyStringH()
{
Space*space=spaceTop;
String*string=stringTop[space->len];
do
{
if(!checkH(space, string))
continue;
putStringH(space, string);
if(!spaceTop)
return 1;
if(tryPutString())
return 1; /*残りも置けた*/
/*駄目だった．．．*/
backStringH(space, string);
}while((string=string->next));
return 0;
}
inline int tryPutAnyStringV()
{
Space*space=spaceTop;
String*string=stringTop[space->len];
do
{
if(!checkV(space, string))
continue;
putStringV(space, string);
if(!spaceTop)
return 1;
if(tryPutString())
return 1; /* 残りも置けた*/
/* 駄目だった．．．*/
backStringV(space, string);
}while((string=string->next));
return 0;
}
#define tryPutAnyString()\
(spaceTop->dir?tryPutAnyStringH():tryPutAnyStringV())
// だめもとで置いてみる
static int tryPutString()
{
Space*space=spaceTop;
String*string;
unsigned int cnt; // 候補の数
String*ret;
#if DEBUG>2
printBoard(board);
#endif
cnt=0;
top:
string=stringTop[space->len];
if(!space->dir)
{
do
{
CHECK_V(space, string, goto nextV);
if(!cnt)
{
cnt=1;
ret=string;
}
else
{
space=space->next;
cnt=0;
if(space)
goto top;
return tryPutAnyString();
}
nextV:
string=string->next;
}while(string);
}
else
{
do
{
CHECK_H(space, string, goto nextH);
if(!cnt)
{
cnt=1;
ret=string;
}
else
{
space=space->next;
cnt=0;
if(space)
goto top;
return tryPutAnyString();
}
nextH:
string=string->next;
}while(string);
}
if(!cnt)
return 0;
putString(space, ret);
if(!spaceTop)
return 1; // 置ききった
if(!tryPutString())
{
backString(space, ret);
return 0;
}
return 1;
}
inline String*findSafeString(const Space*const space)
{
int cnt=0;
String*string=stringTop[space->len];
String*ret=0;
if(space->dir)
{
do
{
CHECK_H(space, string, goto nextH);
if(!cnt)
{
cnt=1;
ret=string;
}
else
return 0;
nextH:
string=string->next;
}while(string);
}
else
{
do
{
CHECK_V(space, string, goto nextV);
if(!cnt)
{
cnt=1;
ret=string;
}
else
return 0;
nextV:
string=string->next;
}while(string);
}
return ret;
}
// crosswordを解く
void answerCrossWord(Board*b)
{
Space*space, *s;
String*string;
boardSize=b->size;
cell=b->cell;
#if DEBUG>1
printBoard(board);
#endif
if(boardSize!=MAX_SIZE)
fastFindAllSpaces();
else
findAllSpaces();
stringNum=b->stringNum;
boardStr=b->str;
// 下準備
calcScores();
initStrings();
makeSpaceList();
// fast solve
space=spaceTop;
do
{
string=findSafeString(space);
s=space;
if(!string)
{
tryPutString(); // slow solve
return;
}
space=space->next;
putString(s, string);
}while(space);
#if DEBUG>1
printBoard(board);
#endif
}
以下もう少し詳しい解説 †
ソース先頭のコメントに，簡単な解説があります．そっちを先に読んでください．
あと，逆アセンブルしたわけではない(したくてもできない)ので，嘘書いてる可能性が高いです．
初日はサンプルをいじって遊んでました．2日目に回答のあるアドレスを調べ，そこからコピーするだけのコードを送ってみましたが，スコアは76万点でした．
最終的なスコアが63万だったので，あまり複雑なことをする余裕が無かった事が分かります．
最終的に提出したコードの大まかな流れは「前処理->確実に置けるものを全部置く->残りを深さ優先探査」です．
- 前処理
- calcScores
Spaceの優先度を計算します．優先度は他のSpaceとの交点の数だけで決めています．
fast solveの後に呼ぶようにすると，たぶん高速化できます．面倒だったのでやってません．．． - initStrings
文字列の長さごとにリストを作っています．
nextへのポインタを使った変なリストですが，insertをスッキリ書けます．
文字列は長さでソートされて届くので，前回計算した長さを利用してstrlenを高速化したつもりでしたが，
サークルのHAL反省会で，全てのSpaceを見つけた時点でstrlenはいらない，と後輩に指摘されました．その通りだと思います - makeSpaceList
scoreでinsertion sortしています．それだけ． 配列の添え字を1から始めることでint i=stringNum; do { insert(&spaces[i]); }while(--i);な風にアクセスしていますが，1000点位しか変わらなかったはずです．
- calcScores
- 置けるかな？
check[HV]関数とCHECK_[HV]マクロで，あるspaceにstringが置けるか調べています．
大量に呼ばれる関数なので，これを高速化するとすごい勢いでスコアが伸びます．
いかにパイプラインをストールさせないかもポイントですが，どんなコードをコンパイラが吐いているのか分からないので，色々と試行錯誤をする必要があります．
変数の値を変更したらしばらく放置，が基本な気がしますが，レジスタ割付か何かの問題で，上手くいかないこともあります．
逆アセンブルしたコードを読みたかったです．．． - 確実におけるほげ
コメントでfast solveとか書いてある部分です．
最初の段階で，場所が一意に決まる文字列は，失敗の可能性を無視して置きます．
スタックとかに控えておく必要がないので，高速に置くことができます．
一つでも文字列が置けると，他のを置ける可能性がありますが，しつこくやっても効率が悪いので，一回走査するだけでやめちゃいます．
こんなのでも，fast solveだけで解けちゃう問題が沢山ありました． - 深さ優先探査
一意における物があれば置く．なければ優先度順に文字列を確定させていきます．
また，一意における物があるか調べるのと一緒に，枝狩もしています．
あるspaceに置けるstringが
1つしか無い ->置く
1つもない ->失敗確定
2個(それ以上は調べない)->他のを探す
あるstringを置くことができるspaceが一つしか存在しない場合も，置けるのが確定ですが
stringには優先度が付けにくいので，効率が悪くやっていません．
一意に置けなかった場合は，優先度順にspaceを選んでいます．
この時，全てのspaceとstringに対してcheckをしておくと
spaceに置ける文字列の数が一番少ない物を選択，とかができますが，
spaceにstringが2種類ある事が分かった時点で切り上げる処理の方が，効果が大きいのでやっていません． - bdnz
PowerPCには「branch decrement not zero」という命令があります．
レジスタをデクリメントして，その値が0以外なら分岐します．
パイプラインがストールしないように，分岐の前にレジスタの値を決めておく事が重要なのですが
bdnzを使える場合は使ったほうがいいです．
unsigned int j=len-1; do { nthChar[len][j][(int)str[j]]++; }while(--j); nthChar[len][j][(int)str[j]]++;あまり巨大なループでは，キャッシュが効かないのでやめましょう． - オフセットの計算を省く
座標をxとyを使って管理すると，少なくとも関数の先頭でx+y*MAX_SIZEの計算が行われます．
これは無駄なので，最初に計算したらoffsetとして持っておきます．
また，構造体のメンバにアクセスする時もoffsetの計算が必要ですが，
一番使うメンバを先頭に置くことで，offsetの計算を省けます．僕の場合はnextです．
当然，複数回使うメンバの値は，ローカル変数にコピーしておきます． - 分岐を減らす
Intel漬けの僕は，分岐減らすことがまず大事，みたいなコードを書こうとしてしまいますが
PowerPCは分岐予測に失敗しても致命的ではないみたいです．
乗算を1回増やして，1回分岐を減らすようなコードを提出した時はスコアが下がりました．
分岐予測がうまくいっていただけかも知れませんがびっくりしました．
ただ，H，Vな関数やBLACKで壁を作ることは効果的だったので，やっぱり分岐を減らすのは大事です．
こんな感じです．気になる所があれば，コメントか掲示板に何か残しておいてください．
50万以上はGecko向けのチューニング勝負な気がします．すごいアルゴリズムを期待していた方，ごめんなさい．
