AOJ181～190

0181 Persistence

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

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

#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
三目並べの勝敗を判定する問題です。

解法
縦横斜めを素朴にチェックするマトリックス*ｃを作るだけです。
ｂの2進数はｗのサブセットになっているのでビット演算を使って両者を判別することは困難です。
かわりにチェックする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)];
	//ｂが３つかｗが３つか並んでたら
               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
占いの問題。
３つの線分が三角形をなすなら面積に応じた結果を返す問題。
数学的部分が終われば後は実装ゲーム。

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

タグ：

+ タグ編集

「AOJ181～190」をウィキ内検索

最終更新：2012年07月11日 13:17

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

0181 Persistence

0182　Beaker

0183 Black-and-White

0184 Tsuruga Castle

0185 Goldbach's Conjecture II

0186 Aizu Chicken

0187　Stoning Fortune

0188　Search

0189　Convenient Location

0190　Eleven Puzzle

c21coterie @ ウィキ

AOJ181～190

更新履歴

メニュー

リンク

他のサービス

0181 Persistence

0182 Beaker

0183 Black-and-White

0184 Tsuruga Castle

0185 Goldbach's Conjecture II

0186 Aizu Chicken

0187 Stoning Fortune

0188 Search

0189 Convenient Location

0190 Eleven Puzzle

0182　Beaker

0187　Stoning Fortune

0188　Search

0189　Convenient Location

0190　Eleven Puzzle