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

「2011年4月」(2011/05/10 (火) 13:18:18) の最新版変更点

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

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

*2011/5/9
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509 
この問題。
シーツの周計を求めるとはどういうことだろう？
シーツの外枠に沿って歩く人がいて一周したときの歩数でシーツの集計を数えるなら外周を数えたことになるだろうか？
シーツを1として、以下のような
00000
01110
01010
01010
01110
00000
場合シーツの外周を求めるとは？
0の所全てを歩くことになるわけだ。
すると、外周に沿って動く状態遷移マシーンを定義してあげて一度通ったポイントは記録しておけばいいのかな？
マシーンは
1　上下左右の1の数を数えて加算していく。
2　上下左右斜めの0のポイントを探して移動する？
外周に沿って動くということを定義するのが大変そうだなこの方法だと？
近傍点のみを判断基準にすると込み入った場所をスルーしてしまう可能性に対処できない。
しかもこの方法だと最悪6000*10000程度の点を記録することになるな。
もっと賢い方法は何だろう？

シートを一枚ずつ追加していく。
今までのシート外周点に関する情報を元に一枚追加した後の外周情報を使う？




*2011/5/8
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1032
うーん、この問題結局幅優先探索で解いたら解けた。
ギリギリ解けただけなのでまだまだ高速化できるらしい。


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


void setMap(int,int);



struct setCourse{
	int size;
	int d;
	bool subjects[21];
	int sum;
	
	bool operator<(const setCourse sc)const{
		if(d<sc.d) return true;
		if(d>sc.d) return false;
		for(int i=0;i<size;i++){
			if(subjects[i]<sc.subjects[i]) return true;
			if(subjects[i]>sc.subjects[i]) return false;
		}
		return false;
	}
	
	void setData(bool* ss,int s,int deep,int tsum){
		size=s;
		memcpy(subjects,ss,s);
		d=deep;
		sum=tsum;
	}
};



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

void setMap(int n,int u){
	int m;
	int tempSubC[21];
	int subC[21];
	int subMs[21];
	int subSet[21][21];
	
	for(int i=0;i<n;i++){
		scanf("%d %d",&subC[i],&subMs[i]);
		tempSubC[i]=subC[i];
		for(int j=0;j<subMs[i];j++){
			scanf("%d",&subSet[i][j]);
		}
	}
	std::sort(tempSubC,tempSubC+n);
	int tsum=0,ansMin=0;
	for(int i=n-1;i>-1;i--){
		tsum+=tempSubC[i];
		if(tsum>=u){
			ansMin=n-i;
			break;
		}
	}
	
	bool tempSet[21];
	for(int i=0;i<n;i++){
		tempSet[i]=(i<ansMin ? true:false);
		//printf("%d ",tempSet[i]);
	}
	std::set<setCourse> scs;
	setCourse sc;
	bool pushOK;
	
	do{
		pushOK=true;
		tsum=0;
		for(int i=0;i<n;i++)
		{
			if(tempSet[i]==true)
			{
				tsum+=subC[i];
				for(int j=0;j<subMs[i];j++)
				{
					if(tempSet[subSet[i][j]]==false)
					{
						pushOK=false;
						break;
					}
				}
			}
			if(pushOK==false) break;
		}
		if(pushOK==true){
			if(tsum>=u){
				printf("%d\n",ansMin);
				return ;
			}
			sc.setData(tempSet,n,ansMin,tsum);
			scs.insert(sc);
		}
	}while(std::prev_permutation(tempSet, tempSet+n));
	
	
	
	std::set<setCourse>::iterator it;
	it=scs.begin();
	
	while(it!=scs.end()){
		sc=(*it);
		for(int i=0;i<n;i++)
		{
			pushOK=true;
			if(sc.subjects[i]==false)
			{
				for(int j=0;j<subMs[i];j++){
					if(sc.subjects[subSet[i][j]]==false){
						pushOK=false;
						break;
					}
				}
			
				if(pushOK==true){
					sc.subjects[i]=true;
					sc.sum+=subC[i];
					sc.d++;
					if(sc.sum>=u){
						printf("%d\n",sc.d);
						return ;
					}
					scs.insert(sc);
					sc.d--;
					sc.sum-=subC[i];
					sc.subjects[i]=false;
				}
			}
		}
		it++;
	}
}









http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
リンク先問題、問題サイズが小さい時だけ解けるコード。
周計を求めるとあるけれどドーナツ型となった場合周計はどうするんだろ？
内部の周も足すんだろうか？
それとも外周だけ計算するんだろうか？

#include<stdio.h>
#include<set>
void setMap(int n,int type);

struct point{
	int x,y;
	bool operator<(const point p)const{
		if(x!=p.x) return x<p.x;
		if(y!=p.y) return y<p.y;
		return false;
	}
};

int main()
{
	int n,type;
	scanf("%d %d",&n,&type);
	while(n!=0 || type!=0){
		setMap(n,type);
		scanf("%d %d",&n,&type);
	}
}
void setMap(int n,int type){
	int x1,y1,x2,y2;
	std::set<point> area;
	point p;
	for(int i=0;i<n;i++){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		for(int i=x1+1;i<x2-1;i++){
			p.x=i;
			p.y=y1;
			area.insert(p);
			p.y=y2-1;
			area.insert(p);
		}
		for(int i=y1;i<y2;i++){
			p.y=i;
			p.x=x1;
			area.insert(p);
			p.y=i;
			p.x=x2-1;
			area.insert(p);
		}
	}
	std::set<point>::iterator it;
	printf("%d\n",area.size());
	if(type==2){
		int dx[]={1,0,-1,0};
		int dy[]={0,1,0,-1};
		int count=0;
		it=area.begin();
		while(it!=area.end()){
			for(int i=0;i<4;i++){
				p.x=(*it).x+dx[i];
				p.y=(*it).y+dy[i];
				if(area.find(p)==area.end()){
					count++;
				}
			}
			it++;
		}
		printf("%d\n",count);
	}
}



*2011/5/6
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1116
ジグソーパズル問題。
一般のｎになっても対応できるようにコードを記述。
我ながら模範解答のようなコードを書けたのではないかと思う。
まあマジックナンバーが多いのが減点だけどコード全体の設計はかなりいい感じ。


#include<stdio.h>
void setMap();
void saiki(int deep);


char peaces[9][5];
char rows[3][4];
char cols[3][4];
char sa='A'-'a';
bool useds[9];
int ans;


int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		setMap();
	}	
}

void setMap(){
	for(int i=0;i<9;i++){
		scanf("%s",peaces[i]);
		useds[i]=false;
	}
	ans=0;
	saiki(0);
	printf("%d\n",ans);
}

void saiki(int deep){
	if(deep==9){
		ans++;
	}
	int x,y;
	x=deep%3;
	y=deep/3;
	bool peaceOK;
	for(int i=0;i<9;i++){
	if(useds[i]==true) continue;
	for(int j=0;j<4;j++){
		peaceOK=true;
		if(y>0){
			if(!(rows[y-1][x]==peaces[i][j]+sa || rows[y-1][x]==peaces[i][j]-sa)){
				peaceOK=false;
			}
		}
		if(x>0){
			if(!(cols[x-1][y]==peaces[i][(j+3)%4]+sa || cols[x-1][y]==peaces[i][(j+3)%4]-sa)){
				peaceOK=false;
			}
		}
		rows[y][x]=peaces[i][(j+2)%4];
		cols[x][y]=peaces[i][(j+1)%4];
		if(peaceOK==true){
			useds[i]=true;
			saiki(deep+1);
			useds[i]=false;
		}
	}	
	}
}





*2011/5/6
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1032
む、難しい。
一番簡単な方法は深さ優先探索である。
各再帰関数では、履修済みデータから現在選ぶことのできる科目を一つ選択しそれを選び、それを履修済みにして次の再帰へ行く。
という方法である。

この時、深さ優先探索で履修単位を基準にメモ化をしておくと計算量が抑えられる。
探索の途中で過去に通ったのと同じ履修単位の組み合わせになったら、そこで探索を打ち切るという方法である。

もっと簡単で賢い方法があるのではないか？
深さ優先探索はお馬鹿な方法なのではないか？

という疑問があるためにこの問題は難しくなる。

深さ優先探索+メモ化探索でチャレンジ、見事玉砕。
この問題の統計データを見るにほとんどがタイムリミットエクスパッション、時間切れ、私もその中の一人と。
うーん、どうやって解けばいいのかな？


見方を変えてみよう。
単位の取り方は全体で2＾20通りの組み合わせ。
これで、可能な単位の取り方不可能な単位の取り方というものを考えていけばいいのである。
2＾20は約１０４万通り*実現可能な組み合わせかのチェックを導入する。
これなら計算量も小さくなんとかなるだろう。

と考え玉砕。
何が悪かったんだろ？
計算量を更に落とすにはどうすればいいんだろう？

#include<stdio.h>
#include<math.h>
void setMap(int,int);

int subC[21];
int subMs[21];
int subSet[21][21];


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

void setMap(int n,int u){
	int m;

	for(int i=0;i<n;i++){
		scanf("%d %d",&subC[i],&subMs[i]);
		for(int j=0;j<subMs[i];j++){
			scanf("%d",&subSet[i][j]);
		}
	}
	int p=0,q,d,ans=200;
	int end=(int)pow(2,(double)(n)),sum;
	bool subOK[21];
	int nowSubSet[21];
	while(p<end){
		q=p;
		p++;
		d=0;
		sum=0;
		
		for(int i=0;i<n;i++){
			if(q&1==1){
				subOK[i]=true;
				sum+=subC[i];
				nowSubSet[d]=i;
				d++;
				if(ans<d) break;
			}else{
				subOK[i]=false;
			}
			q=q>>1;
		}
		
		if(ans<=d || u>sum){
			continue;
		}
		int temp;
		bool okFlag=true;
		for(int i=0;i<d;i++){
			temp=nowSubSet[i];
			for(int j=0;j<subMs[temp];j++){
				if(subOK[subSet[temp][j]]==false){
					okFlag=false;
					break;
				}
			}
			if(okFlag==false) break;
		}
		if(okFlag==true && d<ans){
			ans=d;
		}
	}
	printf("%d\n",ans);
}



以下玉砕コード。
#include<stdio.h>
#include<set>
#include<vector>
#include<algorithm>
void setMap();
int saiki(int deep,int sum);

struct setCourse{
	int size;
	int d;
	bool subjects[21];
	bool operator<(const setCourse sc)const{
		for(int i=0;i<size;i++){
			if(subjects[i]<sc.subjects[i]) return true;
			if(subjects[i]>sc.subjects[i]) return false;
		}
		return false;
	}
	void setData(bool* ss,int s,int deep){
		size=s;
		for(int i=0;i<s;i++) subjects[i]=ss[i];
		d=deep;
	}
};

int n,u;
std::set<setCourse> scs;
bool subjectOK[21];
int subjectC[21];
std::vector<int> subjectSet[21];
int ans;
std::set<setCourse>::iterator sit;


int main(){

	scanf("%d %d",&n,&u);
	while(n!=0 || u!=0)
	{
		setMap();
		scanf("%d %d",&n,&u);
	}
}

void setMap(){
	scs.clear();
	int m,t;
	ans=200;
	for(int i=0;i<n;i++){
		subjectOK[i]=false;
		scanf("%d %d",&subjectC[i],&m);
		subjectSet[i].clear();
	
		for(int j=0;j<m;j++){
			scanf("%d",&t);
			subjectSet[i].push_back(t);
		}
	}
	printf("%d\n",saiki(0,0));
}

int saiki(int deep,int sum){
	if(sum>=u){
		ans=deep<ans ? deep:ans;
		return deep;
	}
	setCourse sc;
	sc.setData(subjectOK,n,0);
	sit=scs.find(sc);
	if(sit!=scs.end()) return (*sit).d;
	
	
	std::vector<int>::iterator it;
	bool nextOK;
	int d=200;
	for(int i=0;i<n;i++){
		if(subjectOK[i]==true) continue;
		nextOK=true;
		it=subjectSet[i].begin();
		while(it!=subjectSet[i].end()){
			if(subjectOK[(*it)]==false){
				nextOK=false;
				break;
			}
			it++;
		}
		if(nextOK==false) continue;
		subjectOK[i]=true;
		d=std::min(d,saiki(deep+1,sum+subjectC[i]));
		subjectOK[i]=false;
	}
	
	sc.setData(subjectOK,n,d);
	scs.insert(sc);
	return d;
}





*2011/5/6
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1014
ｎ個ある源泉からｍ個ある都市へパイプラインを引く問題。
源泉から都市への距離と都市間の距離が与えられるので、源泉から全ての都市へ最短距離でパイプラインをつなげよという問題。
ｎ個の源泉同士が距離0の辺でつながったグラフだと考え、後は源泉と都市をプリム法でつなげていけば解ける。


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

void setMap();
void saiki(int no,int sum);
int map[101][101];
std::set<int> connects;
int n,m,ans;
bool endFlag;
	
int main()
{

	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0){
		setMap();
		scanf("%d %d",&n,&m);
	}
}

void setMap(){
	connects.clear();
	endFlag=false;
	ans=2000000000;
	for(int i=0;i<n+m;i++){
		for(int j=0;j<m;j++)map[i][j]=0;
	}
	for(int i=0;i<n;i++)connects.insert(i);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<m-1;i++){
		for(int j=i+1;j<m;j++){
			scanf("%d",&map[i+n][j]);
			map[j+n][i]=map[i+n][j];
		}
	}
	
	
	saiki(0,0);
	printf("%d\n",ans);
	
}

void saiki(int no,int sum){
	
	connects.insert(no);
	if(connects.size()==(unsigned int)(n+m)){
		endFlag=true;
		ans=std::min(sum,ans);
		return;
	}
	
	std::set<int>::iterator it;
	it=connects.begin();
	int t=10000,nextNo=-1;
	while(it!=connects.end()){
		for(int i=0;i<m;i++){
			if(connects.find(i+n)==connects.end() && map[*it][i]>0){
				if(t>map[*it][i]){
					t=map[*it][i];
					nextNo=i+n;
				}
			}
		}
		it++;
	}
	
	if(nextNo>0){
		saiki(nextNo,sum+t);
		if(endFlag==true) return;
	}
}









*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/11
僕は4流プログラマとしての実力しかない。
工学系の機械設計のような数万を超える関係式を設定するような問題は手も出ないし
バイオ系のような間接的なデータに高度な数学を適用して細胞内部でおこったことや状態を推測するような高度なコードはかけない。
昨今のゲームのすさまじい作りこみを見ると心が折れるほどの能力差を感じる。
事務系や業務系として働くにはそういった方面の知識がない。
金融商品を作ってるような天才や秀才とも縁がない。
漫画だったら駄目駄目ずくしでもそれでも何か大切なものを持ってたりするものだが、現実ではそんなものついぞ目にかかったこともない、。
業界経験もない。

4流プログラマとしてどう働く道を見つけるか？
ということなのである。











*2011/5/9
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509 
この問題。
シーツの周計を求めるとはどういうことだろう？
シーツの外枠に沿って歩く人がいて一周したときの歩数でシーツの集計を数えるなら外周を数えたことになるだろうか？
シーツを1として、以下のような
00000
01110
01010
01010
01110
00000
場合シーツの外周を求めるとは？
0の所全てを歩くことになるわけだ。
すると、外周に沿って動く状態遷移マシーンを定義してあげて一度通ったポイントは記録しておけばいいのかな？
マシーンは
1　上下左右の1の数を数えて加算していく。
2　上下左右斜めの0のポイントを探して移動する？
外周に沿って動くということを定義するのが大変そうだなこの方法だと？
近傍点のみを判断基準にすると込み入った場所をスルーしてしまう可能性に対処できない。
しかもこの方法だと最悪6000*10000程度の点を記録することになるな。
もっと賢い方法は何だろう？

シートを一枚ずつ追加していく。
今までのシート外周点に関する情報を元に一枚追加した後の外周情報を使う？




*2011/5/8
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1032
うーん、この問題結局幅優先探索で解いたら解けた。
ギリギリ解けただけなのでまだまだ高速化できるらしい。


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


void setMap(int,int);



struct setCourse{
	int size;
	int d;
	bool subjects[21];
	int sum;
	
	bool operator<(const setCourse sc)const{
		if(d<sc.d) return true;
		if(d>sc.d) return false;
		for(int i=0;i<size;i++){
			if(subjects[i]<sc.subjects[i]) return true;
			if(subjects[i]>sc.subjects[i]) return false;
		}
		return false;
	}
	
	void setData(bool* ss,int s,int deep,int tsum){
		size=s;
		memcpy(subjects,ss,s);
		d=deep;
		sum=tsum;
	}
};



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

void setMap(int n,int u){
	int m;
	int tempSubC[21];
	int subC[21];
	int subMs[21];
	int subSet[21][21];
	
	for(int i=0;i<n;i++){
		scanf("%d %d",&subC[i],&subMs[i]);
		tempSubC[i]=subC[i];
		for(int j=0;j<subMs[i];j++){
			scanf("%d",&subSet[i][j]);
		}
	}
	std::sort(tempSubC,tempSubC+n);
	int tsum=0,ansMin=0;
	for(int i=n-1;i>-1;i--){
		tsum+=tempSubC[i];
		if(tsum>=u){
			ansMin=n-i;
			break;
		}
	}
	
	bool tempSet[21];
	for(int i=0;i<n;i++){
		tempSet[i]=(i<ansMin ? true:false);
		//printf("%d ",tempSet[i]);
	}
	std::set<setCourse> scs;
	setCourse sc;
	bool pushOK;
	
	do{
		pushOK=true;
		tsum=0;
		for(int i=0;i<n;i++)
		{
			if(tempSet[i]==true)
			{
				tsum+=subC[i];
				for(int j=0;j<subMs[i];j++)
				{
					if(tempSet[subSet[i][j]]==false)
					{
						pushOK=false;
						break;
					}
				}
			}
			if(pushOK==false) break;
		}
		if(pushOK==true){
			if(tsum>=u){
				printf("%d\n",ansMin);
				return ;
			}
			sc.setData(tempSet,n,ansMin,tsum);
			scs.insert(sc);
		}
	}while(std::prev_permutation(tempSet, tempSet+n));
	
	
	
	std::set<setCourse>::iterator it;
	it=scs.begin();
	
	while(it!=scs.end()){
		sc=(*it);
		for(int i=0;i<n;i++)
		{
			pushOK=true;
			if(sc.subjects[i]==false)
			{
				for(int j=0;j<subMs[i];j++){
					if(sc.subjects[subSet[i][j]]==false){
						pushOK=false;
						break;
					}
				}
			
				if(pushOK==true){
					sc.subjects[i]=true;
					sc.sum+=subC[i];
					sc.d++;
					if(sc.sum>=u){
						printf("%d\n",sc.d);
						return ;
					}
					scs.insert(sc);
					sc.d--;
					sc.sum-=subC[i];
					sc.subjects[i]=false;
				}
			}
		}
		it++;
	}
}









http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
リンク先問題、問題サイズが小さい時だけ解けるコード。
周計を求めるとあるけれどドーナツ型となった場合周計はどうするんだろ？
内部の周も足すんだろうか？
それとも外周だけ計算するんだろうか？

#include<stdio.h>
#include<set>
void setMap(int n,int type);

struct point{
	int x,y;
	bool operator<(const point p)const{
		if(x!=p.x) return x<p.x;
		if(y!=p.y) return y<p.y;
		return false;
	}
};

int main()
{
	int n,type;
	scanf("%d %d",&n,&type);
	while(n!=0 || type!=0){
		setMap(n,type);
		scanf("%d %d",&n,&type);
	}
}
void setMap(int n,int type){
	int x1,y1,x2,y2;
	std::set<point> area;
	point p;
	for(int i=0;i<n;i++){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		for(int i=x1+1;i<x2-1;i++){
			p.x=i;
			p.y=y1;
			area.insert(p);
			p.y=y2-1;
			area.insert(p);
		}
		for(int i=y1;i<y2;i++){
			p.y=i;
			p.x=x1;
			area.insert(p);
			p.y=i;
			p.x=x2-1;
			area.insert(p);
		}
	}
	std::set<point>::iterator it;
	printf("%d\n",area.size());
	if(type==2){
		int dx[]={1,0,-1,0};
		int dy[]={0,1,0,-1};
		int count=0;
		it=area.begin();
		while(it!=area.end()){
			for(int i=0;i<4;i++){
				p.x=(*it).x+dx[i];
				p.y=(*it).y+dy[i];
				if(area.find(p)==area.end()){
					count++;
				}
			}
			it++;
		}
		printf("%d\n",count);
	}
}



*2011/5/6
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1116
ジグソーパズル問題。
一般のｎになっても対応できるようにコードを記述。
我ながら模範解答のようなコードを書けたのではないかと思う。
まあマジックナンバーが多いのが減点だけどコード全体の設計はかなりいい感じ。


#include<stdio.h>
void setMap();
void saiki(int deep);


char peaces[9][5];
char rows[3][4];
char cols[3][4];
char sa='A'-'a';
bool useds[9];
int ans;


int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		setMap();
	}	
}

void setMap(){
	for(int i=0;i<9;i++){
		scanf("%s",peaces[i]);
		useds[i]=false;
	}
	ans=0;
	saiki(0);
	printf("%d\n",ans);
}

void saiki(int deep){
	if(deep==9){
		ans++;
	}
	int x,y;
	x=deep%3;
	y=deep/3;
	bool peaceOK;
	for(int i=0;i<9;i++){
	if(useds[i]==true) continue;
	for(int j=0;j<4;j++){
		peaceOK=true;
		if(y>0){
			if(!(rows[y-1][x]==peaces[i][j]+sa || rows[y-1][x]==peaces[i][j]-sa)){
				peaceOK=false;
			}
		}
		if(x>0){
			if(!(cols[x-1][y]==peaces[i][(j+3)%4]+sa || cols[x-1][y]==peaces[i][(j+3)%4]-sa)){
				peaceOK=false;
			}
		}
		rows[y][x]=peaces[i][(j+2)%4];
		cols[x][y]=peaces[i][(j+1)%4];
		if(peaceOK==true){
			useds[i]=true;
			saiki(deep+1);
			useds[i]=false;
		}
	}	
	}
}





*2011/5/6
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1032
む、難しい。
一番簡単な方法は深さ優先探索である。
各再帰関数では、履修済みデータから現在選ぶことのできる科目を一つ選択しそれを選び、それを履修済みにして次の再帰へ行く。
という方法である。

この時、深さ優先探索で履修単位を基準にメモ化をしておくと計算量が抑えられる。
探索の途中で過去に通ったのと同じ履修単位の組み合わせになったら、そこで探索を打ち切るという方法である。

もっと簡単で賢い方法があるのではないか？
深さ優先探索はお馬鹿な方法なのではないか？

という疑問があるためにこの問題は難しくなる。

深さ優先探索+メモ化探索でチャレンジ、見事玉砕。
この問題の統計データを見るにほとんどがタイムリミットエクスパッション、時間切れ、私もその中の一人と。
うーん、どうやって解けばいいのかな？


見方を変えてみよう。
単位の取り方は全体で2＾20通りの組み合わせ。
これで、可能な単位の取り方不可能な単位の取り方というものを考えていけばいいのである。
2＾20は約１０４万通り*実現可能な組み合わせかのチェックを導入する。
これなら計算量も小さくなんとかなるだろう。

と考え玉砕。
何が悪かったんだろ？
計算量を更に落とすにはどうすればいいんだろう？

#include<stdio.h>
#include<math.h>
void setMap(int,int);

int subC[21];
int subMs[21];
int subSet[21][21];


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

void setMap(int n,int u){
	int m;

	for(int i=0;i<n;i++){
		scanf("%d %d",&subC[i],&subMs[i]);
		for(int j=0;j<subMs[i];j++){
			scanf("%d",&subSet[i][j]);
		}
	}
	int p=0,q,d,ans=200;
	int end=(int)pow(2,(double)(n)),sum;
	bool subOK[21];
	int nowSubSet[21];
	while(p<end){
		q=p;
		p++;
		d=0;
		sum=0;
		
		for(int i=0;i<n;i++){
			if(q&1==1){
				subOK[i]=true;
				sum+=subC[i];
				nowSubSet[d]=i;
				d++;
				if(ans<d) break;
			}else{
				subOK[i]=false;
			}
			q=q>>1;
		}
		
		if(ans<=d || u>sum){
			continue;
		}
		int temp;
		bool okFlag=true;
		for(int i=0;i<d;i++){
			temp=nowSubSet[i];
			for(int j=0;j<subMs[temp];j++){
				if(subOK[subSet[temp][j]]==false){
					okFlag=false;
					break;
				}
			}
			if(okFlag==false) break;
		}
		if(okFlag==true && d<ans){
			ans=d;
		}
	}
	printf("%d\n",ans);
}



以下玉砕コード。
#include<stdio.h>
#include<set>
#include<vector>
#include<algorithm>
void setMap();
int saiki(int deep,int sum);

struct setCourse{
	int size;
	int d;
	bool subjects[21];
	bool operator<(const setCourse sc)const{
		for(int i=0;i<size;i++){
			if(subjects[i]<sc.subjects[i]) return true;
			if(subjects[i]>sc.subjects[i]) return false;
		}
		return false;
	}
	void setData(bool* ss,int s,int deep){
		size=s;
		for(int i=0;i<s;i++) subjects[i]=ss[i];
		d=deep;
	}
};

int n,u;
std::set<setCourse> scs;
bool subjectOK[21];
int subjectC[21];
std::vector<int> subjectSet[21];
int ans;
std::set<setCourse>::iterator sit;


int main(){

	scanf("%d %d",&n,&u);
	while(n!=0 || u!=0)
	{
		setMap();
		scanf("%d %d",&n,&u);
	}
}

void setMap(){
	scs.clear();
	int m,t;
	ans=200;
	for(int i=0;i<n;i++){
		subjectOK[i]=false;
		scanf("%d %d",&subjectC[i],&m);
		subjectSet[i].clear();
	
		for(int j=0;j<m;j++){
			scanf("%d",&t);
			subjectSet[i].push_back(t);
		}
	}
	printf("%d\n",saiki(0,0));
}

int saiki(int deep,int sum){
	if(sum>=u){
		ans=deep<ans ? deep:ans;
		return deep;
	}
	setCourse sc;
	sc.setData(subjectOK,n,0);
	sit=scs.find(sc);
	if(sit!=scs.end()) return (*sit).d;
	
	
	std::vector<int>::iterator it;
	bool nextOK;
	int d=200;
	for(int i=0;i<n;i++){
		if(subjectOK[i]==true) continue;
		nextOK=true;
		it=subjectSet[i].begin();
		while(it!=subjectSet[i].end()){
			if(subjectOK[(*it)]==false){
				nextOK=false;
				break;
			}
			it++;
		}
		if(nextOK==false) continue;
		subjectOK[i]=true;
		d=std::min(d,saiki(deep+1,sum+subjectC[i]));
		subjectOK[i]=false;
	}
	
	sc.setData(subjectOK,n,d);
	scs.insert(sc);
	return d;
}





*2011/5/6
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1014
ｎ個ある源泉からｍ個ある都市へパイプラインを引く問題。
源泉から都市への距離と都市間の距離が与えられるので、源泉から全ての都市へ最短距離でパイプラインをつなげよという問題。
ｎ個の源泉同士が距離0の辺でつながったグラフだと考え、後は源泉と都市をプリム法でつなげていけば解ける。


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

void setMap();
void saiki(int no,int sum);
int map[101][101];
std::set<int> connects;
int n,m,ans;
bool endFlag;
	
int main()
{

	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0){
		setMap();
		scanf("%d %d",&n,&m);
	}
}

void setMap(){
	connects.clear();
	endFlag=false;
	ans=2000000000;
	for(int i=0;i<n+m;i++){
		for(int j=0;j<m;j++)map[i][j]=0;
	}
	for(int i=0;i<n;i++)connects.insert(i);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<m-1;i++){
		for(int j=i+1;j<m;j++){
			scanf("%d",&map[i+n][j]);
			map[j+n][i]=map[i+n][j];
		}
	}
	
	
	saiki(0,0);
	printf("%d\n",ans);
	
}

void saiki(int no,int sum){
	
	connects.insert(no);
	if(connects.size()==(unsigned int)(n+m)){
		endFlag=true;
		ans=std::min(sum,ans);
		return;
	}
	
	std::set<int>::iterator it;
	it=connects.begin();
	int t=10000,nextNo=-1;
	while(it!=connects.end()){
		for(int i=0;i<m;i++){
			if(connects.find(i+n)==connects.end() && map[*it][i]>0){
				if(t>map[*it][i]){
					t=map[*it][i];
					nextNo=i+n;
				}
			}
		}
		it++;
	}
	
	if(nextNo>0){
		saiki(nextNo,sum+t);
		if(endFlag==true) return;
	}
}









*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/
今日は敵を表示させてみようまでコードを書く。
うーん理解しながら勉強すると時間がかかるなあ。
前半結構手間の多い処理記述が中心だけど、全ては後半楽をするための処理。
なのだ。