「AOJ181~190」の編集履歴(バックアップ)一覧に戻る

AOJ181~190 - (2012/07/11 (水) 13:17:05) のソース

*0181 Persistence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181
n巻そろった本を1巻から順にm段の本棚に右下から詰めて入れます。
格段の本の幅が小さくなるようないれ方をした時、格段の本の幅の最大の幅がどれくらいとなるか答えよ。
本を詰める順番は1巻から順にし順番を違えないとする。

解法
i段目までm冊目までの本を入れた時、どのような入れ方をしたにせよ、そこまでの本の幅が最小となる入れ方のみを残します。
この考え方で動的計画法で解きます。



 #include<stdio.h>
 #include<algorithm>
 void setData(int m,int n){
	int memo[21][102],w=0;
    for(int i=0;i<21;i++){
        for(int j=0;j<102;j++){
            memo[i][j]=2000000000;
        }
    }
	memo[0][0]=0;
	for(int i=0;i<n;i++){
		scanf("%d",&w);
		memo[0][i+1]=memo[0][i]+w;
	}
	int t1,t2;
	for(int i=1;i<m;i++){
		for(int j=0;j<n;j++){
			for(int k=j+1;k<=n;k++){
				t1=memo[i-1][j];
                t1=t1==2000000000?0:t1;
                t2=memo[0][k]-memo[0][j];
				t1=std::max(t1,t2);
				memo[i][k]=std::min(memo[i][k],t1);
			}
		}
	}
	printf("%d\n",memo[m-1][n]);
 }
 int main(){
	int m,n;
	while(1){
		scanf("%d %d",&m,&n);
		if(m==0 && n==0) break;
		setData(m,n);
	}
 }



----
*0182 Beaker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0182
ビーカーからビーカーへ水を移して、全てのビーカーに一度ずつ水を入れれるかという問題。
解法
この問題は深さ優先探索で適度に枝狩りして解きます。
深さ優先探索は二つのパートに分かれます。
あるBeakerを使って、空で未使用のビーカーに水を分けていくパートと、水の入ったビーカーを選ぶパートです。
水の入ったビーカーを選ぶとき、大きいビーカーから選び、そのビーカーよりも大きくて未使用のビーカーがあればそのビーカーとそれより小さいビーカーを使うのをあきらめてリターンして別の探索に移行します。
この簡単なルールに気づくまで何度もタイムリミットを食らってしまいました。


 #include<stdio.h>
 #include<map>
 #include<vector>
 #include<string.h>
 int inBeakers[51];
 int okBeakers[51];
 int beakerSize[51];
 int n;
 bool allOK;
 int allCount;
 void saiki(int spentBeaker,int measure,int p){
	if(spentBeaker==allCount && measure==0){
		//全てのビーカーを使いきった
		allOK=true;
		return;
	}else if(measure==0){
		//ビーカーの中身を分け終えた
		for(int i=n-1;i>=0;i--){
			if(inBeakers[i]==0 && okBeakers[i]>0)return;
			if(inBeakers[i]>0){
				inBeakers[i]--;
				saiki(spentBeaker,beakerSize[i],n-1);
				if(allOK==true) return;
				inBeakers[i]++;
			}
		}
	}else{
		//ビーカーの中身を分けている途中
		for(int i=p;i>=0;i--){
			if(okBeakers[i]>0 && measure>=beakerSize[i]){
				okBeakers[i]--;
				inBeakers[i]++;
				saiki(spentBeaker+1,measure-beakerSize[i],i);
				if(allOK==true) return;
				inBeakers[i]--;
				okBeakers[i]++;
			}
		}
	}
 }
 void setData(){
	std::map<int,int> beakers;
	std::map<int,int>::iterator it;
	int t;
	allOK=false;
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		if(beakers.find(t)==beakers.end()){
			beakers[t]=1;
		}else{
			beakers[t]++;
		}
	}
	it=beakers.begin();
	allCount=n=0;
	while(it!=beakers.end()){
		okBeakers [n]=(*it).second;
		inBeakers [n]=0;
		beakerSize[n]=(*it).first;
		allCount+=okBeakers[n];
		it++;
		n++;
	}
	okBeakers[n-1]--;
	if(n>1){
		saiki(1,beakerSize[n-1],n-1);
	}else{
		allOK=true;
	}
	printf("%s\n",allOK==true?"YES":"NO");
 }
 int main(){
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData();
	}
 }






----
*0183 Black-and-White
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0183
三目並べの勝敗を判定する問題です。

解法
縦横斜めを素朴にチェックするマトリックス*cを作るだけです。
bの2進数はwのサブセットになっているのでビット演算を使って両者を判別することは困難です。
かわりにチェックする3マスの足し算を使うことにしました。
奇麗なコードを用意出来なかったのが少し残念です。



 #include<stdio.h>
 int main(){
 char i,d[2],s,m[10],*c="3331114201203602";
 int u;
 while(scanf("%s",&m[0])!=EOF){
	if(m[0]=='0')break;
	scanf("%s %s",&m[3],&m[6]);
	d[0]='d';
    d[1]='\0';
	for(i=0;i<8;i++){
		s=c[i+8]%8;
		u=(int)m[s]+(int)m[s+c[i]%8]+(int)m[s+2*(c[i]%8)];
		//bが3つかwが3つか並んでたら
                if(u==3*98 || u==3*119){
			d[0]=u/3;
		}
	}
	printf("%s\n",d[0]=='d'?"NA":d);
 }




----
*0184 Tsuruga Castle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0184
敦賀城に訪れた人の年齢データを元に10歳事に集計する問題です。

解法
何も考えずに集計するだけです。
10の倍数であることを利用して割ることで少しだけコードが短くなります。

 #include<stdio.h>
 int main(){
	int n,y,sums[7],i;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<7;i++)sums[i]=0;
		for(i=0;i<n;i++){
			scanf("%d",&y);
			y=y>60?60:y;
			sums[y/10]++;
		}
		for(i=0;i<7;i++){
			printf("%d\n",sums[i]);
		}
	}
 }









----
*0185 Goldbach's Conjecture II
6以上の偶数を2つの素数の和で表した時何通りの表し方があるかを答える問題。

解法
エラトステネスの篩で素数のリストを生成します。
後は偶数の組み合わせはないので偶数を無視して集計するだけです。


 #include<stdio.h>
 #include<string.h>
 const int max=1000001;
 bool so[max];
 void setSo(){
	memset(so,true,max);
	for(int i=3;i<1001;i+=2){
		if(so[i]==false)continue;
		for(int j=i*3;j<max;j+=i*2){
			so[j]=false;
		}
	}
 }
 int main(){
	int n,sum;
	setSo();
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		sum=0;
		for(int i=3;i<=n/2;i+=2){
			sum+=so[i]&&so[n-i]?1:0;
		}
		printf("%d\n",sum);
	}
 }






----
*0186 Aizu Chicken
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0186
決められた予算と購入量の中、会津地鶏と普通の鶏を賢く購入する問題。

解法
この問題は一見線形計画法の問題に見えますが、変数が少ないためバイナリサーチで解けます。
会津地鶏を買う量を決めれば後は買うものが自動でもとまるという性質を利用して解きます。
もう少し問題が難しくなれば線形計画法を解くコードを書く必要があるでしょう。


 #include<stdio.h>
 void BinarySearch(int q1){
	int b,c1,c2,q2;
	int up=1000000,down=1,mid,ans=0,sum;
	scanf("%d %d %d %d",&b,&c1,&c2,&q2);
	
	do{
		mid=(down+up)/2;
		sum=mid+(b-mid*c1)/c2;
		if(mid>q2 || sum<q1 || b-mid*c1<0){
			up=mid-1;
		}else{
			ans=mid>ans?mid:ans;
			down=mid+1;
		}
	}while(down<=up);
	if(ans>0){
		printf("%d %d\n",ans,(b-ans*c1)/c2);
	}else{
		printf("NA\n");
	}
 }
 int main(){
	int q1;
	while(1){
		scanf("%d",&q1);
		if(q1==0)break;
		BinarySearch(q1);
	}
 }


*0187 Stoning Fortune
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0187
占いの問題。
3つの線分が三角形をなすなら面積に応じた結果を返す問題。
数学的部分が終われば後は実装ゲーム。



 #include<stdio.h>
 #include<math.h>
 struct P{
	double x,y;
 };
 struct Line{
	P p1,p2;
 };
 void crossSet(Line& l1,Line& l2,P& reP){
	P p1,p2,p3,p4;
	p1=l1.p1;
	p3=l1.p2;
	p2=l2.p1;
	p4=l2.p2;//ばらばらなサイトを参考に組み上げたのでこのへん統一感がない
	double s1=(p4.x-p2.x)*(p1.y-p2.y)-(p4.y-p2.y)*(p1.x-p2.x);
	double s2=(p4.x-p2.x)*(p2.y-p3.y)-(p4.y-p2.y)*(p2.x-p3.x);		
	reP.x=p1.x+(p3.x-p1.x)*s1/(s1+s2);
	reP.y=p1.y+(p3.y-p1.y)*s1/(s1+s2);
 }
 bool checkCross(Line& l1,Line& l2){
	P p1,p2,p3,p4;
	p1=l1.p1;
	p2=l1.p2;
	p3=l2.p1;
	p4=l2.p2;
	double d1,d2;
	d1=((p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x)) * ((p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x));
	d2=((p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y) * (p3.x - p1.x)) * ((p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y) * (p3.x - p2.x));
	if(d1==0.0&&d2==0.0)return false;//同一直線上にある
	if(d1<=0.0&&d2<=0.0)return true;//交点を持つ
	return false;
 }
 int main(){
	Line lines[3],l;
	P points[3];
	bool ok;
	while(1){
		for(int i=0;i<3;i++){
			scanf("%lf %lf %lf %lf",&l.p1.x,&l.p1.y,&l.p2.x,&l.p2.y);
			lines[i]=l;
			if(l.p1.x==0&&l.p1.y==0&&l.p2.x==0&&l.p2.y==0){
				return 0;
			}
		}
		ok=true;
		for(int i=0;i<3;i++){
			if(checkCross(lines[i],lines[(i+1)%3])==false){
				ok=false;
			}else{
				 crossSet(lines[i],lines[(i+1)%3],points[i]);
			}
		}
		double ans=0;
		if(ok==true){
			P p1=points[0];
			P p2=points[1];
			P p3=points[2];
			p2.x-=p1.x;
			p2.y-=p1.y;
			p3.x-=p1.x;
			p3.y-=p1.y;
			ans=fabs(p2.x*p3.y-p2.y*p3.x)*0.5;
		}
		//printf("%lf\n",ans);
		if(ans==0.0){
			printf("kyo\n");
		}else if(ans<100000){
			printf("syo-kichi\n");
		}else if(ans<1000000){
			printf("kichi\n");
		}else if(ans<1900000){
			printf("chu-kichi\n");
		}else{
			printf("dai-kichi\n");
		}
	}
 }



----
*0188 Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0188
単調増加数列が与えられるのでその中からバイナリサーチで指定の数字を探す時、サーチが数字を探しだすまでに何回比較が行われるかを出力する問題。
解法
問題の方でサーチ方法が指定されているのでその通りに実装するだけです。


 #include<stdio.h>
 void search(int n){
	int datas[101];
	for(int i=0;i<n;i++){
		scanf("%d",&datas[i]);
	}
	int mid,up=n-1,down=0,t,ans=0,s;
	scanf("%d",&s);
	while(down<=up){
		mid=(down+up)/2;
		t=datas[mid];
		ans++;
		if(t==s){
			break;
		}else if(t<s){
			down=mid+1;
		}else{
			up=mid-1;
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		search(n);
	}
 }







----
*0189 Convenient Location
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0189
各町をつなげる道と移動時間がグラフとして与えられる。
ある町から出発してある他の町へ行くとき、移動時間の総計がもっとも小さくなる町を選び、その合計時間を求めよという問題です。
詳しくは問題分を読んでください。

解法
グラフの問題なのでワーシャルフロイド法で解きます。




 #include<stdio.h>
 #include <algorithm>
 int timeMax=1000000000;
 void calc(int g[11][11],int maxNo){
	int t;
	for(int y=0;y<maxNo;y++){
		for(int x=0;x<maxNo;x++){
			if(g[x][y]==timeMax)continue;
			for(int i=0;i<maxNo;i++){
				t=g[x][y]+g[y][i];
				if(t<g[x][i]){
					g[x][i]=t;
				}
			}
		}
	}
 }
 void setData(int n){
	int g[11][11];
	for(int i=0;i<11;i++){
		for(int j=0;j<11;j++){
			g[i][j]=i==j?0:timeMax;
		}
	}
	int a,b,c,maxNo=0;
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&a,&b,&c);
		g[a][b]=g[b][a]=c;
		maxNo=std::max(b,maxNo);
		maxNo=std::max(a,maxNo);
	}
	maxNo++;
	calc(g,maxNo);
	int ans=timeMax,sum,ansNo;
	for(int i=0;i<maxNo;i++){
		sum=0;
		for(int j=0;j<maxNo;j++){
			sum+=g[i][j];
		}
		if(ans>sum){
			ans=sum;
			ansNo=i;
		}
	}
	printf("%d %d\n",ansNo,ans);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData(n);
	}
 }







----
*0190 Eleven Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0190 
イレブンパズルの盤面が与えられるので完成までに何手かかるかを答える問題。

解法
こういった問題の一つの方法として完成状態から逆算して至れる全状態をはじめに計算しておくという方法があります。
今回は計算量が多く普通に探索すると時間切れになります。
そろった状態から10手目までと、与えられた盤面の状態から10手目までを探す両側探索で実装することにしてみました。
両者の探索結果に共通集合が見出されれば20手以内でクリアできると判別します。
枝がりをいれるとコードが早くメモリ使用量も少なくなるようですので他のサイトを参考にしてください。



 #include<iostream>
 #include<map>
 #include<string>
 #include<queue>
 #include <algorithm>
 int move[13][4]={	{ 2,-1,-1,-1},{ 2, 5,-1,-1},{ 0, 1, 6, 3},{ 2, 7,-1,-1},{ 5,-1,-1,-1},{ 1, 4, 9, 6},
					{ 2, 5,10, 7},{ 3, 6,11, 8},{ 7,-1,-1,-1},{ 5,10,-1,-1},{ 6, 9,12,11},{ 7,10,-1,-1},
					{10,0,0,0}};
 std::map<std::string,int> memo;
 void setData(){
	std::queue<std::string> qu;
	std::string state="0123456789abc",next;	
	for(int i=0;i<12;i++){
		state[i]=i+'0';
	}
	state[12]='0';
	qu.push(state);
	memo[state]=0;
	int turn;
	while(!qu.empty()){
		state=qu.front();
		qu.pop();
		turn=memo[state]+1;
		if(turn>10) break;
		for(int i=0;i<13;i++){
			if(state[i]=='0'){
				for(int j=0;j<4;j++){
					if(move[i][j]==-1) break;
					std::swap(state[i],state[move[i][j]]);
					if(memo.find(state)==memo.end()){
						memo[state]=turn;
						qu.push(state);
					}
					std::swap(state[i],state[move[i][j]]);
				}
			}
		}
	}
 }
 int search(std::string s){
//両側探索で実装
	std::queue<std::string> qu;
	std::map<std::string,int> tempMemo;
	qu.push(s);
	tempMemo[s]=0;
	int turn;
	while(!qu.empty()){
		s=qu.front();
		qu.pop();
		turn=tempMemo[s];
		
		if(memo.find(s)!=memo.end()){
			return turn+memo[s];
		}
		turn++;
		if(turn>11) break;
		for(int i=0;i<13;i++){
			if(s[i]=='0'){
				for(int j=0;j<4;j++){
					if(move[i][j]==-1)break;
					std::swap(s[i],s[move[i][j]]);
					if(tempMemo.find(s)==tempMemo.end()){
						tempMemo[s]=turn;
						qu.push(s);
					}
					std::swap(s[i],s[move[i][j]]);
				}
			}
		}
	}
	return 21;
 }
 bool setMap(std::string& s){
	s="0123456789abc";
	int nums[13];
	std::cin>>nums[0];
	if(nums[0]==-1)return false;
	s[0]='0'+nums[0];
	for(int i=1;i<13;i++){
		std::cin>>nums[i];
		s[i]='0'+nums[i];
	}
	return true;
 }
 int main(){
	setData();
	std::string s;
	while(setMap(s)){
		int n=search(s);
		if(n>20){
			std::cout<<"NA\n";
		}else{
			std::cout<<n<<"\n";
		}
	}
 }