2011/1/31
問題では英単語一万単語が与えられ、その一万単語を使ったループを探すことになります。
まともに探索をすると、ある単語の次に来る単語が400単語、その次も400単語で大雑把にいって400＾25*399＾25*、、、*2＾25*1＾25という恐ろしい探索を行うことになってしまう。
これを以下に小さく探索するかという問題になります。
この問題の解き方。
a,,,zまでと名付けられた点をもつグラフを考えます。
このグラフ上で、単語の開始文字から終了文字へ矢印をつけたしｇとします。
ループができるということは、開始文字と終了文字の文字の数は一致する。
abc cde efa aa
という場合c の次はｃで始まる単語があるわけで一対一対応となります。
この条件を満たせばグラフに枝先がないことが保証されます。
1 単語の先頭文字の出現頻度でヒストグラフをとりこれをAとする。
2 単語の末尾文字の出現頻度でヒストグラフをとりこれをBとする。
３ AとBの形が完全に一致すればgには枝先がないことが保証されます。
これだけだとgが複数のループに分かれる場合を除去できません。
4 これを 除去するために、ｇ上の文字のうち→が存在する点を最低一回ずつ通るルートRを探します。
これが見つかれば、シリトリはループを持つことが保証されます。
なぜなら、Rが見つかった場合、Rのルートでできるグラフに３を満たしながら矢印を付け加えてｇを再現していくと全てのルートが見つかるからです。
g上の2点を点Ai、Ajとします。AiからAjへ一本→を加えると仮定しますとAjでは、３を満たすためにAjからでる矢印を付け加えなくてはいけません。
これを繰り返すと→がAiに戻るまでこの→作業は繰り返されます。
これは全ての点で成立します。
よって4がみつかれば全ての単語を使うループが見つかることになるわけです。
コード製作者 堀江伸一
〒兵庫県加古川市加古川町南備後79-16
以下リンク先問題で合格したコード。
<stdio.h>
<string.h>
void setMap(int n);
void search(int,int,int);
int map[26][26];
bool moveOK[26];
bool searchOK;
int headCount[26];
int tealCount[26];
int startPoint;
int main(void)
{
int n;
scanf("%d",&n);
while(n>0){
setMap(n);
scanf("%d",&n);
}
}
void setMap(int n){
char in[33];
searchOK=false;
startPoint=0;
for(int i=0;i<26;i++){
moveOK[i]=true;
headCount[i]=0;
tealCount[i]=0;
for(int j=0;j<26;j++)
{
map[i][j]=0;
}
}
int s,e;
for(int i=0;i<n;i++)
{
scanf("%s",in);
s=in[0]-'a';
e=in[strlen(in)-1]-'a';
map[s][e]++;
headCount[s]++;
tealCount[e]++;
}
bool okFlag=true;
int min=10001;
for(int i=0;i<26;i++){
if(headCount[i]!=tealCount[i]){
okFlag=false;
break;
}
if(min>headCount[i] && headCount[i]>0){
min=headCount[i];
startPoint=i;
}
}
if(okFlag==false){
printf("NG\n");
return;
}
int upper=0;
for(int i=0;i<26;i++){
if(map[i][i]>0){
map[i][i]=1;
}
if(headCount[i]>0){
upper++;
}
}
search(startPoint,upper,0);
if(searchOK==true){
printf("OK\n");
}else{
printf("NG\n");
}
return ;
}
void search(int p,int upper,int deep)
{
if(upper==deep && startPoint==p){
searchOK=true;
return ;
}
if(upper>=deep && searchOK==false){
int nextDeep=deep;
if(moveOK[p]==true){
nextDeep++;
}
moveOK[p]=false;
for(int i=p;i<26+p;i++){
int j=i%26;
if(map[p][j]>0){
map[p][j]--;
search(j,upper,nextDeep);
if(searchOK==true){
break;
}
map[p][j]++;
}
}
moveOK[p]=true;
}
}
2010/1/27
この問題を解こうと今日は論理的には正しいが単語数が1万になると制限時間内に計算が終わらない処理を書いてしまった。
この問題はかなり難しい。
計算量に関する厳密な知識が要求されるのかも？
単語と単語の番号を管理する構造体を作り、この構造体を要素とする配列を2つ確保し、片方は単語の末尾を基準にもう片方は単語の先頭を基準にSortし、先頭と末尾の関係をバイナリサーチで求めるといいのかもしれない？
1 単語は入力された順番に0からNoを割り振る
2 データを保存する構造体は、単語の先頭 char型、単語の末尾char型、単語のno intの３を保持する
3 データは同じものが2種類用意され、片方は単語の先頭を基準にSort、もう片方は単語の末尾を基準にSortしておく。
4 この構造体の配列を使ってデータを探索する。
5 問題になるのは、複数の単語が候補に挙がった時、どういう基準でSearchしていくのかである。それにこれだけだと計算量が十分に下がらない可能性もある？
6 良く考えたら？単語の先頭と単語の末尾の文字のヒストグラフをとって両者が完全に同じならいいのではないか？
7 でもこれだとループが二つ以上に分かれる場合の対処ができない
8 map＜char ,vector<char> ＞ として、mapのkeyを単語末尾、 vectorを次の単語の末尾としておけば計算量が小さくなるかもしれない？それにこれだと探索処理の記述が楽だ。
9 int[26][26]な配列を用意するのも手かも？列に単語末尾文字、行に次の単語の末尾文字とし、この組み合わせでヒストグラフをとり表にしておく、この表を探索すれば計算量がマシにはなる
10 問題は8,9どちらが計算量が小さくなるだろうか？
考えたら今日かいた処理、10000*10000なんて2次元配列を使ってグラフを表しこのグラフを探索してるものな。
遅いわけだ。
しかしまあ、現実的なプログラムというのはこんな簡単な問題よりもはるかに難しい問題が多数あって、そういう問題に挑戦できるようになるためには、こういう簡単な問題を解いてレベルアップしてからじゃないとだめだなとは思うのでこういう問題も大事だと思う。
以下今日書いた恥ずかしい処理。
<stdio.h>
<string.h>
void setMap(int n);
bool searchOK;
bool **Map;
bool *moveOK;
void search(int p,int deep,int n);
int main(void)
{
int n;
scanf("%d",&n);
while(n>0){
setMap(n);
scanf("%d",&n);
}
}
void setMap(int n){
Map=new bool*[n];//シリトリの末尾から最初への移動ができるかのチェック
moveOK=new bool[n];
char *startC=new char[n+1];//シリトリの最初
char *tailC =new char[n+1];//シリトリの末尾
char in[33];
searchOK=false;
for(int i=0;i<n;i++){
Map[i]=new bool[n];
moveOK[i]=true;
for(int j=0;j<n;j++){
Map[i][j]=false;
}
}
for(int i=0;i<n;i++){
scanf("%s",in);
tailC[i]=in[strlen(in)-1];
startC[i]=in[0];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(tailC[i]==startC[j] && i!=j){
Map[i][j]=true;
}
}
}
search(0,0,n);
if(searchOK==true){
printf("OK\n");
}else{
printf("NG\n");
}
for(int i=0;i<n;i++){
delete [] Map[i];
}
delete [] Map;
delete [] moveOK;
delete [] startC;
delete [] tailC;
}
void search(int p,int deep,int n)
{
if(deep==n && p==0){
searchOK=true;
}else if(searchOK==false && n>deep && moveOK[p]==true){
moveOK[p]=false;
for(int i=0;i<n;i++){
if(Map[p][i]==true){
search(i,deep+1,n);
}
}
moveOK[p]=true;
}
}
2010/1/16
2010/1/10
落とし穴がある問題。
a,b,c,dは背反なので、３つチェックできたら答えが分かる。
どれを排除するかとなる。
まずｂは簡単。
三角の頂点が円の中心からｒ以下の距離にあればいいのだから。
a,c,dをどういいかえるかとなる。
a,c,dの判別式は結構落とし穴があるな。
2011/1/9
うーん？
勘だけど、木構造を使うのかな？
まず隣り合う2件の家間の距離を考え、これをSiとする。
Siを繋げる、繋げないで考えると、２＾（ｎ-1)通り存在することになる。
これでは計算量が多そうで駄目なのは明白。
直感的には短いSiから繋げていって出来る線分の個数がｎになった時点で止めれば上手く動きそうな気もする？
でも一軒に一つ発電機をつける場合も考えないといけない。
家がｎ、発電機がｎ-1のとき、一番長いSiを除去すればいい。
家がｎ、発電機がｎ-２のとき、2番目に長いSiまでを除去すればいいのではないか？
と考えたらいいのかも。
明日コーディングしてみよう。
(2011/1/10注釈、短時間で考え方を見つけるまでに挑戦したのだけど、明らかに間違っていた。
書いた後すぐに答えに気づいたのだが正しい答えは、家N軒-発電機K個だけ、Siを短いほうから足していったのが答えになる。大事なのはSortだけ)
最終更新：2011年01月31日 13:30
