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

AOJ181~190 - (2011/08/29 (月) 14:27:27) の1つ前との変更点

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

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

 *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
 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){
+ #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]);
 		}
 	}
  }