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

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

AOJ181~190 - (2011/08/29 (月) 14:27:27) の編集履歴(バックアップ)


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