2007:01 02 03 04 05 06 07 08 09 10 11 12
2008:01 02 03 04 05 06 07 08 09 10 11 12
2009:01
最新
blog/2008-01-31
音の倍速再生 †
元の音->FFT->周波数をいじる->時間をいじる->IFFT
な感じですると，IFFTのつなぎ目にノイズが乗る．
で，IFFTの時にオーバーラップ+両端を萎めて加算とかやると，繋ぎ目が目立たなくなりました．
論文を漁るべきな気もしますが，どうしようかな．
こんなのもあるみたいです．
http://keizai.yokkaichi-u.ac.jp/~ikeda/research/picola-jp.html
blog/2008-01-30
帰ってきた †
眠い．
マセマティカ便利だ †
結構面白いです．グラフや音が簡単に出せます．
簡単なグラフを書くだけなら，gnuplotより楽な気もします．
もっと安ければいいのになぁ．
blog/2008-01-29
ほげ †
廃トンネルで後輩の実験の手伝い．
blog/2008-01-27
飲み会 †
gotoの妹が遊びにきたので，みんなで飲んだ．
酔いが回った頃に，goto妹とタイピング勝負．完敗．
悔しいのでがんばろう．．．
目標:e-typing長文タイピングで500
blog/2008-01-26
プログラムで世界へ挑戦(IOI) †
02/22放送予定．ネット配信はいつかな．
http://sc-smn.jst.go.jp/8/bangumi.asp?i_series_code=B073310&i_renban_code=005
blog/2008-01-23
うはぁ †
起きたら16時過ぎ．もう駄目だ．
サークル †
kstm.orgの部室でアルミの板を削ったりしてました．
今日は失敗気味．何をやってるかは，まだ秘密らしいです．
blog/2008-01-22
取材商法 †
http://yamcha.seesaa.net/article/79916832.html
おもしろいなぁ．
kstm.orgにも，ヤフオクでリース切れのマシン売るの手伝いませんか？ ウハウハですよ
みたいな人が，直接きたりして面白かったです．
http://www.asahi.com/digital/internet/OSK200801070022.html
23歳になりました †
blog/2008-01-21
ksk †
http://d.hatena.ne.jp/nyaasan/20080121/p1
kskはHSP界で有名人だとかMeshiが言っていた事を思い出しました．
ICPCのパーティには，他にも有名人がゴロゴロいたしなぁ．
kstm.orgは最近地味なので，もっと色々がんばると良いかなぁと思います．
コメントのflappphysさんは「On Lisp」の翻訳をした方みたいです．
積読です．ごめんなさい
あと，指導教官にもプロコンに出てたことがばれててびっくりしました．
履歴書 †
を書き始めた．めんどくさいです．
「使用経験があるプログラミング言語とOS」を書く必要があるのですが
OS．．．LinuxとかMacOS Xも一ヶ月ずつ位は使ってましたが，使用経験には入らない気がするので，WindowsとFreeBSDな気がします．
プログラミング言語はもっと微妙で，普段触るのはC/C++, Haskell, Schemeだけ．
Perlは普段触らないし，PHPはpukiwiki言語，Javaとか大嫌いです．
とか思ってたら，Google Code Jam 2005にJavaで参加してたみたいです．
http://www.f13g.com/?%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0/Java/Google%20Code%20Jam%202005
MicrosoftのあれはC#で参加しましたし，うはー．
書いていてLLが足りないなぁとか思いました．shで済ませる事が多いです．
すごく眠かった †
寝不足だったので，すごく眠い1日でした...
blog/2008-01-19
HALプロコンの賞金と賞状と記念品 †
が届いた．記念品の演算子マグカップが一番嬉しかったりします．
賞金の1万円は，ラスベガスで遊ぶ費用になる予定です．
にゃあさんがマグカップの写真をUPしてました．
http://d.hatena.ne.jp/nyaasan/20080119
こんなのです．
blog/2008-01-18
HAL研究所 プログラミングコンテスト2007 結果発表 †
http://www.hallab.co.jp/progcon/2007/
HAL研プロコンの結果と，上位3人のコードが発表されました．
私のコードは昨日張ったのと全く同じなのでどうでもいいです．
投稿回数は899回と全参加者で最多。
やっぱりそうなのかw
ishimuraさんもtaiyouさんも，関数呼び出しをかなり抑えてますね．
上位の人はマクロかinline多用だと信じていたので意外でした．
詳細は今から読んでみます．
3人とも †
コードは全く違いますが，考えてた事は似ている気がします．
taiyouさんのジョーカーの考え方は素直だなぁと思いました．
その辺の工夫は，ishimuraさんや僕のコードでも，こっそり行われてます．
ishimuraさんが文字の配置を後回しにしていたのがショックです．
めんどくさい感じがプンプンしてたので，実装しませんでした^^; 効果あるんですねぇ
あと，みなさん再帰をやめて自前のスタックに積んでるみたいですが，
スタックポインタをコンパイラに書いてもらうか，自分で書くかの違いであまり変わらないような．．．とか思いました．
違うのは，戻り先のアドレス分位じゃないかなぁ
dshow.h †
DirectShow Filterでもほげって見ようと思って
#include<dshow.h>
とかやったら，ddraw.hが無いと怒られた．
DirectShow SDKはDirectX SDKからPlatformSDKにわざわざ移しておいて，これはひどいと思った．
- プロコンで検索してやってきました。お疲れ様でした。途中からの追い上げ、参りました。来年は勝てるようにがんばります。 -- taiyou 2008-01-21 16:12:19 (月)
- 後半は思いついた事をとにかく試してみる感じでした．来年は総合優勝したいです．お互いがんばりましょう．お疲れ様でした． -- Safii 2008-01-21 19:47:34 (月)
blog/2008-01-17
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向けのチューニング勝負な気がします．すごいアルゴリズムを期待していた方，ごめんなさい．
blog/2008-01-16
サークル †
怪しい工作をした後，中庭で怪しい集会．
blog/2008-01-15
パスポート †
パスポートを受け取りに行った．道路が凍結してる気がしたので自転車で．
帰りに英語の参考書を買った．色々立ち読みしたけれど，何がいいのかさっぱり分からない．
誰か英語(特に英会話)の良い勉強法を教えてください．
家に英語しか喋れない人がいた時は，拙かったけれど英語で会話ができてた気がする．
ただ，その状況を作れる気がしない．
blog/2008-01-14
ずっと寝てた気がする †
起きた後は，サイエンスチャンネルをずっと見てた．
blog/2008-01-13
HAL †
http://d.hatena.ne.jp/ranha/20080111/1199984594
FCは，ranhaさんと(たぶん)同じ手法．
「入れる事ができる文字列が最少なものを選ぶ」も試してみたけれど，スコアが下がったのでやめた．最初に交点の数を数えて，並び替えただけです．
BJはめんどくさそうなのでやめました(ぇ
問題の規模が小さかったので，複雑な前処理は無駄な感じでした．
HAL履歴 †
提出したコードのスコアを，グラフにしてみました．
たまに０になっているのは，errorを返された時です．
全部で899回もsubmitしています．いくらなんでも多すぎです．
blog/2008-01-12
のもと †
http://www.nomotto.net/
のもとに行ってきた．僕は何も買わなかった
お土産会 †
お土産を持ち寄って，食べたり飲んだり．
7人集まって，日本酒が７升以上あったので，どう考えても飲みきれない．
シンガポールのカップヌードルがおいしかった．スポーツドリンクはひどい．
blog/2008-01-11
寝坊 †
寝坊してゼミに遅刻した
UNIX MAGAZINE Classic with DVD †
先生が献本で貰ったらしい．で，それをもらった．
blog/2008-01-10
HAL †
賞状、賞金『プロコン2007オリジナル「演算子の優先順位と結合規則」マグカップ』がもらえるみたい．楽しみだ．
blog/2008-01-09
鍵忘れた †
2週間ほど実家に帰ってました．
で，実家にかばんを置いてきたのですが，その中に家の鍵が入ってた．
今晩はkoumaのお世話になります．
入れた †
大家さんに鍵を借りて入った．
HAL研プログラミングコンテスト2007終わり †
http://www.hallab.co.jp/progcon/2007/
総合2位，学生部門1位で終わったみたいです．賞金は変わりませんが，ishimuraさんに負けたのが悔しいです．
2 Safii 2008-01-10 11:59:43 631355
締め切り17秒前にスコア更新しました^^
kskも10位に入ったみたいです
blog/2008-01-08
EXILIM EX-F1いいなぁ †
http://dc.casio.jp/product/exilim/ex_f1/
最大1200FPSで撮影可能．
http://dc.casio.jp/product/exilim/ex_f1/hispeed_mov.html
こんなのが自分で撮れたら気持ちいいなぁ．3月発売，ラスベガス前に買ってしまいそうだ．．．
相撲 筋肉という鎧をまとった男たち@サイエンスチャンネル †
http://sc-smn.jst.go.jp/8/bangumi.asp?i_series_code=B033401&i_renban_code=005
身長、体重ともに、私たちより数倍も大きな力士たち。
TODO:力士の身長を調べる
blog/2008-01-07
HALプロコン2007 †
何となくいじった部分が良かったらしく，5000点アップ．
学生3位から一気に1位になった．総合1位のishimuraさんとの差は4500
ばいばいThinkPad †
http://www.technobahn.com/cgi-bin/news/read2?f=200801071732
ライセンスの関係で，ThinkPadの名前が使えなくなるのは知っていましたが，デザインも全面的に変えるんですね．
トラックポイントはまぁ良いのですが，キーボードが気になるなぁ．
- 「thinkpad」ブランドしばらく使えるはず，今回の発表はコンシューマ向けの新しいブランド「IdeaPad」が出来ましたよ．ってだけですよ -- meshi 2008-01-09 02:33:01 (水)
- ThinkPad->IdeaPadってわけではないんですね．ThinkPadのロゴも，契約延長とかできるような契約みたいです -- Naoki 2008-01-09 14:16:17 (水)
blog/2008-01-06
まかーおばあちゃん †
スリープ状態のMacにつながっているプリンタ/スキャナ複合機を操作すると，スリープから復帰するMacを見てひどい仕様だなぁと思った．
スリープ状態のMacにつながっているデジカメを抜いたら，スリープから復帰するMacを見て信じられないなぁと思った．
blog/2008-01-05
そういえば †
正月の英語でしゃべらナイトが始まった頃にフラフラになったんだ．．．
最初しか見てないからニコニコとかで探してみよう
http://guideline.livedoor.biz/archives/51018243.html
HALプロコン2007 †
ずーっとコードを見てると，スコアが伸びる．と言っても2000点とかですが．．．
http://www.google.co.jp/support/jobs/bin/static.py?page=why-jp.html&sid=interview
TopCoderをやるべきかも！ 初級中級ってICPCだとどれくらいの問題ですか？
30秒後の追記:もう2000点追加できてた
blog/2008-01-04
少し体調が良くなった †
朝起きたらおなかの調子は良い感じ．頭痛はまだ残ってたので，テレビをみてぼーっと過ごす．
「そんなの関係ねぇ」とか「どんだけー」を初めて見た．研究室の人たちはこれを真似してたのか．．．
バラエティーばかりでつまらない．のだめスペシャルは面白かった．
HAL †
寝る前にチェック．差をつけられてる・・・ いくつかコードを書いて送ったら100点アップ．もう駄目だ．．．
blog/2008-01-03
体調不良その２ †
一日中布団の中．夜，おかゆを少し食べた．
blog/2008-01-02
体調不良 †
朝から体の調子がおかしいと思ったら，夜中にひどいことになった．
妹と同じ症状なので，救急車で運ばれないようにがんばった．
blog/2008-01-01
あけおめ †
ことよろ
コーディング初め †
HAL研のやつ．というか，年越しコーディングだった．
妙なチューニングが多くて微妙^^; 何かアイデアが降りてこないと，1位に届かない気がしてきました
夢 †
クワガタに中指を切られて焦って眼が覚めた．
今年は †
ラスベガスで大もうけ．成功したらニート．まぁたぶん失敗するので，今後の生活費を稼ぐ方法も考えておく．
ICFPがんばる．
思いついているネタを消化する．
修論はまぁ何とかなるでしょう．
