※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ181~190」の編集履歴(バックアップ)一覧に戻る
AOJ181~190」を以下のとおり復元します。
*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
ビーカーからビーカーへ水を移して、全てのビーカーに一度ずつ水を入れれるかという問題。

解法
正答まであと少しのコードを書いています。
タイムリミッドを喰らうのでどう高速化しようか思案中です。


 #include<stdio.h>
 #include<map>
 #include<vector>
 int inBeakers[51];
 int okBeakers[51];
 int beakerSize[51];
 bool butBeakers[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){
		std::vector<int> memo;
		for(int i=0;i<n;i++){
			if(inBeakers[i]>0 && butBeakers[i]==false){
				inBeakers[i]--;
				saiki(spentBeaker,beakerSize[i],n-1);
				if(allOK==true) return;
				butBeakers[i]=true;
				inBeakers[i]++;
				memo.push_back(i);
			}
		}
		for(int i=0;i<memo.size();i++){
			butBeakers[memo[i]]=false;
		}
	}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;
		butBeakers[n]=false;
		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の倍数であることを利用して割ることで少しだけコードが短くなります。

 #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);
	}
 }






----
*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
イレブンパズルの盤面が与えられるので完成までに何手かかるかを答える問題。

解法
こういった問題の一つの方法として完成状態から逆算して至れる全状態をはじめに計算しておくという方法があります。
今回は計算量が多く普通に探索すると時間切れになります。
そろった状態から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";
		}
	}
 }

復元してよろしいですか?