「2011年4月」の編集履歴（バックアップ）一覧はこちら

2011年4月 - (2011/05/04 (水) 14:53:26) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*2011/5/4
http://rose.u-aizu.ac.jp/onlinejudge/ProblemInfo.jsp?id=0528
最長一致文字列問題。
有名問題なので考え方を偶々知っていたので楽楽解答。

この問題の難しいところは回答者リストのランキング。
私のコードは0.0017秒でメモリ800ｋｂ使用という普通の解き方。

メモリ使用量ほぼ0、コード実行速度0.0000という人がいること。
どうやって計算量抑えたんだろ？
メモリ使用量低減は状態遷移マシーンで解いて落としたのだと思う。
計算量はどうしたんだろ、かなり謎である？
この問題計算量を落とせばメモリが増え、メモリを抑えると計算量が増えるイメージあるんだけどな。

とりあえず私のコード。


#include<stdio.h>
#include<string.h>

int main()
{
	char t1[4001],t2[4001];
	int memo[2][4001];
	int len1,len2;
	int num;
	
	
	while(scanf("%s",t1)!=EOF){
		scanf("%s",t2);
		len1=strlen(t1);
		len2=strlen(t2);
		num=0;
		for(int i=0;i<len1;i++)memo[0][i]=0;
		for(int i=1;i<=len2;i++){
			memo[i%2][0]= t2[i-1]==t1[0] ? 1:0;
			for(int j=1;j<len1;j++){
				if(t2[i-1]==t1[j]){
					memo[i%2][j]=memo[(i+1)%2][j-1]+1;
					num=memo[i%2][j]>num ? memo[i%2][j]:num;
				}else{
					memo[i%2][j]=0;
				}
			}
		}
		printf("%d\n",num);
	}
}




*2011/5/3
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0202
リンク先問題を解くコード。
少しだけ塩らしい高速化をしてるが基本的にはオーソドックスなメモ化探索で解法。
高速化も適当なのでコード実行速度は普通の6/95位。
１位の人は僕の３倍速いけどどうやって計算してるんだろ？
少し気になる。
これ１次元だから楽勝だけど、ｎ次元のメモ化とかどうするのか想像もつかないなあ。
実務だったらｎ次元のメモカだよなあ。


#include <stdio.h>
#include <algorithm>

void setSo();
void calc(int,int);

bool so  [1000001];
bool sums[1000001];

int main(){
	int n,x;
	setSo();
	scanf("%d %d",&n,&x);
	while(n!=0 && x!=0){
		calc(n,x);
		scanf("%d %d",&n,&x);
	}
}

void calc(int n,int x){
	int foods[31];
	for(int i=0;i<n;i++){
		scanf("%d",&foods[i]);
	}
	std::sort(foods,foods+n);
	int p,max=0;
	sums[0]=true;
	for(int i=1;i<=x;i++){
		sums[i]=false;
		p=0;
		while(foods[p]<=i && p<n){
			if(sums[i-foods[p]]==true){
				sums[i]=true;
				break;
			}
			p++;
		}
		if(sums[i]==true && so[i]==true){
			max=i;
		}
	}
	if(max>0){
		printf("%d\n",max);
	}else{
		printf("NA\n");
	}
}

void setSo(){
	for(int i=2;i<1000001;i++)
		so[i]=i%2;
	int k;
	for(int i=3;i<1000001;i+=2){
		if(so[i]==true){
			k=i*2;
			for(int j=i*3;j<1000001;j+=(k)){
				so[j]=false;
			}
		}
	}
	so[0]=true;
	so[1]=false;
	so[2]=true;
}





http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0212&lang=jp
？？？
この問題解き方すら思いつかない。
探索でやったら組み合わせ数が爆発するし？
貪欲法はダメみたいだし。
ナップザックやメモ化が使えるとも思えないし。


*2010/5/3
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2007
リンク先問題賢い方法を記述するとめんどくさくなりそうなので最悪の方法で解いてみた。
これより遅いタイムがあるらしいがこれより悪い方法を思いつかない。
私よりコード実行速度の遅い人はどんなコードを上げたのだろう？
気になる。
全探索より遅い方法なんて想像もつかない。
#include <stdio.h>
#include <algorithm>
int calcTuriSen(int s);
void setMap(int n);

int main()
{
	int n;
	scanf("%d",&n);
	while(n!=0){
		setMap(n);
		scanf("%d",&n);
		if(n==0) break;
		printf("\n");
	}
}
	
void setMap(int n){
	int d[4],ans[4];
	int sum,coinSum;
	int ansSum=1000;
	for(int i=0;i<4;i++) scanf("%d",&d[i]);
	
	
	for(int i=0;i<=d[0];i++){
	for(int j=0;j<=d[1];j++){
	for(int k=0;k<=d[2];k++){
	for(int l=0;l<=d[3];l++){
		sum=(i*10+j*50+k*100+l*500);
		if(sum-n>=0){
			coinSum=-(i+j+k+l);
			coinSum+=calcTuriSen(sum-n);
			if(coinSum<ansSum){
				ansSum=coinSum;
				ans[0]=i;
				ans[1]=j;
				ans[2]=k;
				ans[3]=l;
			}
		}
	}
	}
	}
	}
	int coins[]={10,50,100,500};
	for(int i=0;i<4;i++){
		if(ans[i]>0){
			printf("%d %d\n",coins[i],ans[i]);
		}
	}
	
}


int calcTuriSen(int s){
	int ans=0;
	ans=s/500;
	s%=500;
	ans+=s/100;
	s%=100;
	ans+=s/50;
	s%=50;
	ans+=s/10;
	s%=10;
	ans+=s/5;
	s%=5;
	ans+=s;
	return ans;
}




*2011/4/30
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0116
リンク先問題を解くコード。
相当高速化したつもりのコードが下記。
しかし世の中の壁は厚かった。
実行速度２６位普通である。
どこかもう少し高速化できるらしい。


#include<stdio.h>
int map[503][503];

void setMap(int h,int w){
	char t;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			scanf(" %c",&t);
			if(t=='.'){
				map[i][j]=1;
			}else{
				map[i][j]=0;
			}
		}
	}
	for(int i=0;i<=h;i++)map[i][0]=map[i][w+1]=0;
	for(int i=0;i<=w;i++)map[0][i]=0;

	int lp,rp,cp,sum=0,max=0;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(map[i][j]!=0) map[i][j]=map[i-1][j]+1;
		}
		for(int j=1;j<=w;j++){
			if(map[i][j]!=0){
//おそらくこの辺を高速化できると思われ。
				cp=map[i][j];
				lp=rp=1;
				while(map[i][j-lp]>=cp) lp++;
				while(map[i][j+rp]>=cp) rp++;
				sum=cp*(rp+lp-1);
				max=max<sum ? sum:max;
			}
		}
	}
	printf("%d\n",max);
}

int main()
{
	int w,h;
	scanf("%d %d",&h,&w);
	while(h!=0 && w!=0){
		setMap(h,w);
		scanf("%d %d",&h,&w);
	}
}




*2011/4/25
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049
リンク先問題を時折思い出して解法を考えるも全く計算量を落とす方法が分からない。
家の数が9件なら中学生でも着眼点一つで解ける。
10軒だと難しい。
計算量を落とす方向でコードを色々いじくってみる。
大体のデータで正しい答えを出すが、たまに間違った答えを出すコードとか出来たけど、必ず正しい答えを出すコードじゃないと駄目だしな。



#include <stdio.h>
#include <list>
#include <algorithm>
#include <set>

int calcLen(std::list<int> homePerm,int n);
void setMap(int n);
int map[10][10];
int ans;
	
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		setMap(n);
	}
}
int calcLen(std::list<int> homePerm,int n){
	int hp[10];
	int lens[10];
	int i=0;
	std::list<int>::iterator it;
	it=homePerm.begin();
	while(it!=homePerm.end()){
		hp[i]=(*it);
		it++;
		i++;
	}
	
	
	for(int i=0;i<n;i++) lens[i]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
		}
	}
	return lens[n-1];
}

void saiki(std::list<int> homePerm,int n,int deep){
	if(n==deep){
		if(ans==-1){
			ans=calcLen(homePerm,deep);
		}else{
			ans=std::min(ans,calcLen(homePerm,deep));
		}
		return ;
	}
	int tempAns=-1;
	std::list<int> homePermCand[11][100];
	
	int ansCount[11];
	for(int i=0;i<11;i++) ansCount[i]=0;
	
	std::list<int>::iterator it;
	std::list<int>::iterator it2;
	int t;
	
	bool endFlag=false;
	int tempPerm[11];
	it=homePerm.begin();
	for(int i=0;it!=homePerm.end();i++){
		tempPerm[i]=(*it);
		it++;
	}
	
	bool skipFlag;
	for(int k=0;k<n;k++)
	{
		skipFlag=false;
		for(int l=0;l<deep;l++){
			if(k==tempPerm[l]) skipFlag=true;
		}
		if(skipFlag==true) continue;
		it=homePerm.begin();
		endFlag=false;
		while(endFlag==false)
		{
			it2=homePerm.insert(it,k);
			t=calcLen(homePerm,deep);
			if(tempAns==-1){
				tempAns=t;
				homePermCand[k][ansCount[k]]=homePerm;
				ansCount[k]++;
			}else if(tempAns==t){
				homePermCand[k][ansCount[k]]=homePerm;
				ansCount[k]++;
			}else if(tempAns>t){
				tempAns=t;
				homePermCand[k][0]=homePerm;
				ansCount[k]=1;
			}
			
			homePerm.erase(it2);
			if(it==homePerm.end()){
				endFlag=true;
			}else{
				it++;
			}
		}
	}
	for(int k=0;k<deep;k++){
	for(int i=0;i<ansCount[k];i++){
		saiki(homePermCand[k][i],n,deep+1);
	}
	}
}

void setMap(int n){

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//データの読み込み
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//より遠ざけたい人を基準に
			map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
		}
	}
	ans=-1;
	std::list<int> homePerm;
	
	homePerm.clear();
	if(n==1){
		printf("0\n");
	}else{
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j){
				homePerm.clear();
				homePerm.push_back(i);
				homePerm.push_back(j);
				saiki(homePerm,n,2);
			}
		}
	}
	printf("%d\n",ans);
	}
}

*2011/4/13
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049
リンク先は恐ろしく正答率の低いプログラマ向けの問題。
長期間一人しか正答者がいなかった難問。
正答者の数が増えたのは最近である。
統計情報を見ても不正解でグラフが真っ赤。

といっても世間的にはそんなに難しくはない問題なのかも。
本当に実力のある人は北京大学のオンラインジャッジとか、Google主催のオンラインジャッジ（ネット上でプログラマ向けの大会や問題集を扱ってるサイト）にいるから世間的にはたいしたことないのだろう。

AOJには実力のあるプログラマがそんなにいないから正解率が低いにすぎない。
AOJに集まる人にとっては難問だった、程度にすぎないのかも。

私もこの問題に挑戦。
この問題世間的には簡単に分類されるのだろうけど、私には難しく答えが出せない。

正しい答えを出すところまではいってるはずなんだけど、実行時間が長すぎて不正解を喰らう。
コードを効率化する方法がわからない。

家の数が１０軒でも全探索で10！*45程度の計算量　３６０万*45回の計算量になる。
どうやって計算量を落とせばいいんだ？


#include <algorithm>
#include <stdio.h>
void setMap(int n);

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		setMap(n);
	}
}

void setMap(int n){
	int map[10][10];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//データの読み込み
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//より遠ざけたい人を基準に
			map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
		}
	}
	int lens[10];//ある並びで家が並んだ時の各人の家の位置
	int *hp=new int[n];/各人の家の並び順
	int min=2100000000;//21億
	for(int i=0;i<n;i++) hp[i]=i;
	
	do{
		for(int i=0;i<n;i++) lens[i]=0;
		//各人の家が特定の並び順になった時、家をぎちぎちに詰めた場合の最短の長さを求める処理
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<i;j++){
				lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
			}
		}
		min=std::min(lens[n-1],min);
	}while(std::next_permutation(hp, hp+n));//家の全ての並び順を求める
	printf("%d\n",min);//答え
	delete [] hp;
}

*2011/4/4
http://dixq.net/rp/
今日からリンク先を参考にSTG作りを開始。
今日はボードの表示まで完了。

良いサイトである。
設計図をきちんと引いてゲームを作るとどれだけうれしいかが実感できる導入。
多人数で開発を分担できるプログラム開発とは何かが分かる設計。
ゲーム作りのみならず、プログラムを書く時cppファイルをどう分けていくかというアプリ開発の基本が身に付く感じ。
しかも段階を追って学習できるので、C++の基礎が終わっている人なら一人でも学習できる親切設計。
学習に必要な時間も決して長くはない。
解説が高校生でもわかるほどにやさしい。
これで無料！
驚くばかりにいい感じのサイトである。

名前　堀江伸一
住所　兵庫県加古川市加古川町南備後79-16

*2011/4/5
http://dixq.net/rp/
今日は敵を表示させてみようまでコードを書く。
うーん理解しながら勉強すると時間がかかるなあ。
前半結構手間の多い処理記述が中心だけど、全ては後半楽をするための処理。
なのだ。

*2011/5/4
http://rose.u-aizu.ac.jp/onlinejudge/ProblemInfo.jsp?id=0528
最長一致文字列問題。
有名問題なので考え方を偶々知っており楽楽解答。

この問題の難しいところは回答者リストのランキング。
私のコードは実行速度0.0017秒でメモリ800ｋｂ使用という普通の解き方。

メモリ使用量ほぼ0、コード実行速度0.0000という人がいること。
どうやって計算量抑えたんだ？
メモリ使用量低減は状態遷移マシーンで解いて落としたのだと思う。
計算量はどうしたんだろ、かなり謎である？
この問題計算量を落とせばメモリが増え、メモリを抑えると計算量が増えるイメージあるんだけどな。
難しそう。
とりあえず私のコード。


#include<stdio.h>
#include<string.h>

int main()
{
	char t1[4001],t2[4001];
	int memo[2][4001];
	int len1,len2;
	int num;
	
	
	while(scanf("%s",t1)!=EOF){
		scanf("%s",t2);
		len1=strlen(t1);
		len2=strlen(t2);
		num=0;
		for(int i=0;i<len1;i++)memo[0][i]=0;
		for(int i=1;i<=len2;i++){
			memo[i%2][0]= t2[i-1]==t1[0] ? 1:0;
			for(int j=1;j<len1;j++){
				if(t2[i-1]==t1[j]){
					memo[i%2][j]=memo[(i+1)%2][j-1]+1;
					num=memo[i%2][j]>num ? memo[i%2][j]:num;
				}else{
					memo[i%2][j]=0;
				}
			}
		}
		printf("%d\n",num);
	}
}




*2011/5/3
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0202
リンク先問題を解くコード。
少しだけ塩らしい高速化をしてるが基本的にはオーソドックスなメモ化探索で解法。
高速化も適当なのでコード実行速度は普通の6/95位。
１位の人は僕の３倍速いけどどうやって計算してるんだろ？
少し気になる。
これ１次元だから楽勝だけど、ｎ次元のメモ化とかどうするのか想像もつかないなあ。
実務だったらｎ次元のメモカだよなあ。


#include <stdio.h>
#include <algorithm>

void setSo();
void calc(int,int);

bool so  [1000001];
bool sums[1000001];

int main(){
	int n,x;
	setSo();
	scanf("%d %d",&n,&x);
	while(n!=0 && x!=0){
		calc(n,x);
		scanf("%d %d",&n,&x);
	}
}

void calc(int n,int x){
	int foods[31];
	for(int i=0;i<n;i++){
		scanf("%d",&foods[i]);
	}
	std::sort(foods,foods+n);
	int p,max=0;
	sums[0]=true;
	for(int i=1;i<=x;i++){
		sums[i]=false;
		p=0;
		while(foods[p]<=i && p<n){
			if(sums[i-foods[p]]==true){
				sums[i]=true;
				break;
			}
			p++;
		}
		if(sums[i]==true && so[i]==true){
			max=i;
		}
	}
	if(max>0){
		printf("%d\n",max);
	}else{
		printf("NA\n");
	}
}

void setSo(){
	for(int i=2;i<1000001;i++)
		so[i]=i%2;
	int k;
	for(int i=3;i<1000001;i+=2){
		if(so[i]==true){
			k=i*2;
			for(int j=i*3;j<1000001;j+=(k)){
				so[j]=false;
			}
		}
	}
	so[0]=true;
	so[1]=false;
	so[2]=true;
}





http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0212&lang=jp
？？？
この問題解き方すら思いつかない。
探索でやったら組み合わせ数が爆発するし？
貪欲法はダメみたいだし。
ナップザックやメモ化が使えるとも思えないし。


*2010/5/3
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2007
リンク先問題賢い方法を記述するとめんどくさくなりそうなので最悪の方法で解いてみた。
これより遅いタイムがあるらしいがこれより悪い方法を思いつかない。
私よりコード実行速度の遅い人はどんなコードを上げたのだろう？
気になる。
全探索より遅い方法なんて想像もつかない。
#include <stdio.h>
#include <algorithm>
int calcTuriSen(int s);
void setMap(int n);

int main()
{
	int n;
	scanf("%d",&n);
	while(n!=0){
		setMap(n);
		scanf("%d",&n);
		if(n==0) break;
		printf("\n");
	}
}
	
void setMap(int n){
	int d[4],ans[4];
	int sum,coinSum;
	int ansSum=1000;
	for(int i=0;i<4;i++) scanf("%d",&d[i]);
	
	
	for(int i=0;i<=d[0];i++){
	for(int j=0;j<=d[1];j++){
	for(int k=0;k<=d[2];k++){
	for(int l=0;l<=d[3];l++){
		sum=(i*10+j*50+k*100+l*500);
		if(sum-n>=0){
			coinSum=-(i+j+k+l);
			coinSum+=calcTuriSen(sum-n);
			if(coinSum<ansSum){
				ansSum=coinSum;
				ans[0]=i;
				ans[1]=j;
				ans[2]=k;
				ans[3]=l;
			}
		}
	}
	}
	}
	}
	int coins[]={10,50,100,500};
	for(int i=0;i<4;i++){
		if(ans[i]>0){
			printf("%d %d\n",coins[i],ans[i]);
		}
	}
	
}


int calcTuriSen(int s){
	int ans=0;
	ans=s/500;
	s%=500;
	ans+=s/100;
	s%=100;
	ans+=s/50;
	s%=50;
	ans+=s/10;
	s%=10;
	ans+=s/5;
	s%=5;
	ans+=s;
	return ans;
}




*2011/4/30
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0116
リンク先問題を解くコード。
相当高速化したつもりのコードが下記。
しかし世の中の壁は厚かった。
実行速度２６位普通である。
どこかもう少し高速化できるらしい。


#include<stdio.h>
int map[503][503];

void setMap(int h,int w){
	char t;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			scanf(" %c",&t);
			if(t=='.'){
				map[i][j]=1;
			}else{
				map[i][j]=0;
			}
		}
	}
	for(int i=0;i<=h;i++)map[i][0]=map[i][w+1]=0;
	for(int i=0;i<=w;i++)map[0][i]=0;

	int lp,rp,cp,sum=0,max=0;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(map[i][j]!=0) map[i][j]=map[i-1][j]+1;
		}
		for(int j=1;j<=w;j++){
			if(map[i][j]!=0){
//おそらくこの辺を高速化できると思われ。
				cp=map[i][j];
				lp=rp=1;
				while(map[i][j-lp]>=cp) lp++;
				while(map[i][j+rp]>=cp) rp++;
				sum=cp*(rp+lp-1);
				max=max<sum ? sum:max;
			}
		}
	}
	printf("%d\n",max);
}

int main()
{
	int w,h;
	scanf("%d %d",&h,&w);
	while(h!=0 && w!=0){
		setMap(h,w);
		scanf("%d %d",&h,&w);
	}
}




*2011/4/25
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049
リンク先問題を時折思い出して解法を考えるも全く計算量を落とす方法が分からない。
家の数が9件なら中学生でも着眼点一つで解ける。
10軒だと難しい。
計算量を落とす方向でコードを色々いじくってみる。
大体のデータで正しい答えを出すが、たまに間違った答えを出すコードとか出来たけど、必ず正しい答えを出すコードじゃないと駄目だしな。



#include <stdio.h>
#include <list>
#include <algorithm>
#include <set>

int calcLen(std::list<int> homePerm,int n);
void setMap(int n);
int map[10][10];
int ans;
	
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		setMap(n);
	}
}
int calcLen(std::list<int> homePerm,int n){
	int hp[10];
	int lens[10];
	int i=0;
	std::list<int>::iterator it;
	it=homePerm.begin();
	while(it!=homePerm.end()){
		hp[i]=(*it);
		it++;
		i++;
	}
	
	
	for(int i=0;i<n;i++) lens[i]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
		}
	}
	return lens[n-1];
}

void saiki(std::list<int> homePerm,int n,int deep){
	if(n==deep){
		if(ans==-1){
			ans=calcLen(homePerm,deep);
		}else{
			ans=std::min(ans,calcLen(homePerm,deep));
		}
		return ;
	}
	int tempAns=-1;
	std::list<int> homePermCand[11][100];
	
	int ansCount[11];
	for(int i=0;i<11;i++) ansCount[i]=0;
	
	std::list<int>::iterator it;
	std::list<int>::iterator it2;
	int t;
	
	bool endFlag=false;
	int tempPerm[11];
	it=homePerm.begin();
	for(int i=0;it!=homePerm.end();i++){
		tempPerm[i]=(*it);
		it++;
	}
	
	bool skipFlag;
	for(int k=0;k<n;k++)
	{
		skipFlag=false;
		for(int l=0;l<deep;l++){
			if(k==tempPerm[l]) skipFlag=true;
		}
		if(skipFlag==true) continue;
		it=homePerm.begin();
		endFlag=false;
		while(endFlag==false)
		{
			it2=homePerm.insert(it,k);
			t=calcLen(homePerm,deep);
			if(tempAns==-1){
				tempAns=t;
				homePermCand[k][ansCount[k]]=homePerm;
				ansCount[k]++;
			}else if(tempAns==t){
				homePermCand[k][ansCount[k]]=homePerm;
				ansCount[k]++;
			}else if(tempAns>t){
				tempAns=t;
				homePermCand[k][0]=homePerm;
				ansCount[k]=1;
			}
			
			homePerm.erase(it2);
			if(it==homePerm.end()){
				endFlag=true;
			}else{
				it++;
			}
		}
	}
	for(int k=0;k<deep;k++){
	for(int i=0;i<ansCount[k];i++){
		saiki(homePermCand[k][i],n,deep+1);
	}
	}
}

void setMap(int n){

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//データの読み込み
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//より遠ざけたい人を基準に
			map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
		}
	}
	ans=-1;
	std::list<int> homePerm;
	
	homePerm.clear();
	if(n==1){
		printf("0\n");
	}else{
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j){
				homePerm.clear();
				homePerm.push_back(i);
				homePerm.push_back(j);
				saiki(homePerm,n,2);
			}
		}
	}
	printf("%d\n",ans);
	}
}

*2011/4/13
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049
リンク先は恐ろしく正答率の低いプログラマ向けの問題。
長期間一人しか正答者がいなかった難問。
正答者の数が増えたのは最近である。
統計情報を見ても不正解でグラフが真っ赤。

といっても世間的にはそんなに難しくはない問題なのかも。
本当に実力のある人は北京大学のオンラインジャッジとか、Google主催のオンラインジャッジ（ネット上でプログラマ向けの大会や問題集を扱ってるサイト）にいるから世間的にはたいしたことないのだろう。

AOJには実力のあるプログラマがそんなにいないから正解率が低いにすぎない。
AOJに集まる人にとっては難問だった、程度にすぎないのかも。

私もこの問題に挑戦。
この問題世間的には簡単に分類されるのだろうけど、私には難しく答えが出せない。

正しい答えを出すところまではいってるはずなんだけど、実行時間が長すぎて不正解を喰らう。
コードを効率化する方法がわからない。

家の数が１０軒でも全探索で10！*45程度の計算量　３６０万*45回の計算量になる。
どうやって計算量を落とせばいいんだ？


#include <algorithm>
#include <stdio.h>
void setMap(int n);

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		setMap(n);
	}
}

void setMap(int n){
	int map[10][10];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//データの読み込み
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//より遠ざけたい人を基準に
			map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
		}
	}
	int lens[10];//ある並びで家が並んだ時の各人の家の位置
	int *hp=new int[n];/各人の家の並び順
	int min=2100000000;//21億
	for(int i=0;i<n;i++) hp[i]=i;
	
	do{
		for(int i=0;i<n;i++) lens[i]=0;
		//各人の家が特定の並び順になった時、家をぎちぎちに詰めた場合の最短の長さを求める処理
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<i;j++){
				lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
			}
		}
		min=std::min(lens[n-1],min);
	}while(std::next_permutation(hp, hp+n));//家の全ての並び順を求める
	printf("%d\n",min);//答え
	delete [] hp;
}

*2011/4/4
http://dixq.net/rp/
今日からリンク先を参考にSTG作りを開始。
今日はボードの表示まで完了。

良いサイトである。
設計図をきちんと引いてゲームを作るとどれだけうれしいかが実感できる導入。
多人数で開発を分担できるプログラム開発とは何かが分かる設計。
ゲーム作りのみならず、プログラムを書く時cppファイルをどう分けていくかというアプリ開発の基本が身に付く感じ。
しかも段階を追って学習できるので、C++の基礎が終わっている人なら一人でも学習できる親切設計。
学習に必要な時間も決して長くはない。
解説が高校生でもわかるほどにやさしい。
これで無料！
驚くばかりにいい感じのサイトである。

名前　堀江伸一
住所　兵庫県加古川市加古川町南備後79-16

*2011/4/5
http://dixq.net/rp/
今日は敵を表示させてみようまでコードを書く。
うーん理解しながら勉強すると時間がかかるなあ。
前半結構手間の多い処理記述が中心だけど、全ては後半楽をするための処理。
なのだ。