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

AOJ241~250 - (2013/10/19 (土) 05:52:12) のソース

*0246 Bara-Bara Manju
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0246

解法
今のところ予測。
まず全部の数を数えて袋詰めにして残ったまんじゅうの数で動的計画法をおこなう。
1~9の重さのまんじゅうの個数をn1~n9とする
このときまず9の重さのまんじゅうを0~n9まで使って10を作る組み合わせを全部検討し、これを作り終えたら残った9を全部廃棄する。
1~8の残ったまんじゅうの組み合わせが残りこの残り数を主キーとして動的計画法を立てる。
次は主キーを一つ一つ検証して8を0~最大数まで使うことにきめた場合で袋を作ッた場合を計算し同様に8を全部廃棄する。
これを1まで計算したらギリギリのメモリ使用量でクリアできるのではないか?
と思うがどうだろう?


*0241 Quaternion Multiplication
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0241
四元数の2つ組が与えられるので積を計算して返せという問題。
マトリックスに対応表を作れば難しい式を書かなくて済みます。
4元数の式を再帰下降構文解析で解釈し計算結果を出力せよという問題を出されたら100%解く自信がない。


 #include<stdio.h>
 #include<math.h>
 #include<string.h>
 //1=0,i=1,j=2,k=3,
 //-1=4,-i=5,-j=6,-k=7の対応表
 int set[4][4]={	{0,1,2,3},
		{1,4,3,6},
		{2,7,4,1},
		{3,2,5,4}};
 void calc(){
	//1,i,j,k,-1,-i,-j,-kに分けて集計する
	int ans[8],k1[4],k2[4];
	memset(ans,0,sizeof(ans));
	for(int i=0;i<4;i++)scanf("%d",&k1[i]);
	for(int i=0;i<4;i++)scanf("%d",&k2[i]);
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			ans[set[i][j]]+=k1[i]*k2[j];
		}
	}
	//分けた分を整えて出す
	for(int i=0;i<4;i++)printf("%s%d",i==0?"":" ",ans[i]-ans[4+i]);
	printf("\n");
 }
 void setData(int n){
	while(n--)calc();
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		setData(n);
	}
 }



*0242 Input Candidates
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0242
携帯電話の文字入力候補の簡易版を作る問題。
入力された文字をMapを使ってカウントしてSetをつかって入力回数の多い順に並べ直すだけです。



 #include<stdio.h>
 #include<string>
 #include<set>
 #include<map>
 struct WD{
	int count;
	std::string word;
	bool operator<(const WD& wd)const{
		if(count!=wd.count)return count>wd.count;
		return word<wd.word;
	}
 };
 void search(int n){
	char w[22],c;
	std::set<WD> memo[30];
	std::set<WD>::iterator itS;
	std::map<std::string,int> wdCount;
	std::map<std::string,int>::iterator itM;
	WD wd;
	while(n){
		scanf("%s%c",w,&c);
		if(c=='\n')n--;
		if(wdCount.find(w)==wdCount.end()){
			wdCount[w]=1;
		}else{
			wdCount[w]++;
		}
	}
	for(itM=wdCount.begin();itM!=wdCount.end();itM++){
		wd.word=(*itM).first;
		wd.count=(*itM).second;
		c=wd.word[0]-'a';
		memo[c].insert(wd);
	}	
	scanf("%s",w);
	c=w[0]-'a';
	if(memo[c].empty()){
		printf("NA\n");
	}else{
		int count=0;
		for(itS=memo[c].begin();count<5&&itS!=memo[c].end();itS++,count++){
			printf("%s%s",count==0?"":" ",(*itS).word.c_str());
		}
		printf("\n");
	}
	
 }
 int main(){
	int n;
	while(1){
		scanf("%d" ,&n);
		if(n==0)break;
		search(n);
	}
 }




*0243 Filling Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0243
ボタンを押して色を変えていくパズルの最短手数を求めよという問題。

解法
RGBどの色でも色をそろえたという点で共通しており次の色の決定も自由です。
これを利用して色をそろえた部分を全部Sとして表し後は色のそろえ方のパタンを2重再帰で全探索してみました。
探索状態を保存し同じ状態で同じ手数かそれ以上なら探索を打ち切ります。
シンプルな問題である分実装者の思考力やテクニックが試される問題のようで、正答者コード実行時間のばらつきが大きい問題でした。



 #include<stdio.h>
 #include<string.h>
 #include<map>
 int x,y;
 int dxs[]={1,0,-1,0};
 int dys[]={0,1,0,-1};
 int ans=1000;
 
 struct S{
 	char board[11][11];
 	bool operator<(const S& s)const{
 		for(int i=0;i<y;i++){
 			for(int j=0;j<x;j++){
 				if(board[i][j]!=s.board[i][j])return board[i][j]<s.board[i][j];
 			}
 		}
 		return false;
 	}
 	void set(char b[11][11]){
 		memcpy(board,b,121);
 	}
 };
 std::map<S,int> memo;
 
 void print(char board[11][11]){
 	for(int i=0;i<y;i++){
 		for(int j=0;j<x;j++){
 			printf("%c",board[i][j]);
 		}
 		printf("\n");
 	}
 	int a;
 	scanf("%d",&a);
 	printf("\n");
 }
 
 int saiki2(char board[11][11],char changeColor,int px,int py){
 	if(px<0||x<=px||py<0||y<=py)return 0;
 	int re=0;
 	
  	if(changeColor==board[py][px]){
 		board[py][px]='S';
 		re++;
 	}else{
 		return 0;
 	}
 	for(int i=0;i<4;i++){
 		re+=saiki2(board,changeColor,px+dxs[i],py+dys[i]);
 	} 
 	return re;
 }
  
 void saiki1(char board[11][11],char changeColor,int turn){
 	char nextBoard[11][11],c;
 	memcpy(nextBoard,board,121);
 	//print(board);
 	int all=0,changeOk=0,t;
 	for(int py=0;py<y;py++){
 		for(int px=0;px<x;px++){
 			c=board[py][px];
 			if(c=='S'){
 				all++;
 				for(int i=0;i<4;i++){
  					int nx=px+dxs[i];
 					int ny=py+dys[i];
 					t=saiki2(nextBoard,changeColor,nx,ny);
 					if(t>0)changeOk=1;
 					all+=t;
 				}
 			}
 		}
 	}
 	S s;
 	s.set(nextBoard);
 	if(memo.find(s)!=memo.end()&&memo[s]<=turn)return ;
 	memo[s]=turn;
 	if(all==x*y){
 		if(ans>turn)ans=turn;
 	}else if(changeOk==1){
 		saiki1(nextBoard,'R',turn+1);
 		saiki1(nextBoard,'G',turn+1);
 		saiki1(nextBoard,'B',turn+1);
 	}
 }
 
 int main(){
 	char board[11][11],c,text[100];
 	while(1){
 		scanf("%d %d%c",&x,&y,&c);
 		if(x==0&&y==0)break;
 		for(int py=0;py<y;py++){
 			for(int px=0;px<x;px++){
 				scanf("%c%c",&board[py][px],&c);
 			}
 		}
 		int change=saiki2(board,board[0][0],0,0);
 		ans=x*y;
 		if(change==x*y){
 			printf("0\n");
 		}else{
 			memo.clear();
 			saiki1(board,'R',1);
 			saiki1(board,'G',1);
 			saiki1(board,'B',1);
 			printf("%d\n",ans);
 		}
 		scanf("%[^0123456789]",text);
 	}
 }




*0244 Hot Spring Trip
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0244
グラフで表されたバス路線があり辺には運賃が設定されています。
1つ飛ばした先の停留所まで一度だけ無料で乗れるチケットがあるとき目的地まで最小の運賃で移動するにはどうすれば良いか。
その時の運賃を求めよという問題。

ダイクストラ法を少し改良して、停留所を表す点をチケットを使用済みの点、使用前の点と2倍に増やせば解けます。
グラフのつながりを表す変数を隣接行列で持ったために計算量が少しだけ膨らみました。
それを除けば教科書的なベーシックな答えだと思います。



 #include<stdio.h>
 #include<queue>
 #include<string.h>
 #include <algorithm>
 struct state{
	int no,cost,mode;//今いる地点、払った金額、チケット使用済みか?
	bool operator<(const state& s)const{
		return cost<s.cost;
	}
 };
 void calc(int n,int m){
	std::priority_queue<state> pq;
	int a,b,c;
	int con[102][102];//2地点間のコスト、つながってない場合0
	int ans[2][102];//ダイクストラ法の答えの記憶
	int mymax=10000000;	
	//チケット使用済み、チケット使用前、今の位置、次の位置の4次元で管理してもいいけど1枚なので
	//特殊処理で済ます
	//データの読み込みと初期化
	memset(con,0,sizeof(con));
	for(int i=1;i<=n;i++)ans[0][i]=ans[1][i]=mymax;
	ans[0][1]=0;//スタート地点の設定
	//printf("%d %d>",n,m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&a,&b,&c);
		con[a][b]=con[b][a]=c;
	}
	//printf("?");
	//優先順位付きダイクストラ法を行う
	state s,nextS;
	s.cost=s.mode=0;
	s.no=1;
	pq.push(s);
	while(!pq.empty()){
		s=pq.top();
		pq.pop();
		if(ans[s.mode][s.no]<s.cost)continue;//コストが上回った
		for(int i=1;i<=n;i++){
			c=con[s.no][i];
			if(c==0)continue;//路線がつながってない
			nextS.mode=s.mode;//次の地点の設定
			nextS.cost=c+s.cost;
			nextS.no  =i;
			if(s.mode==0){
				//無料チケットを使ってない
				if(ans[0][i]>nextS.cost){
					//無料チケットを使わない
					ans[0][i]=nextS.cost;
					pq.push(nextS);
				}
				//無料チケットを使う
				for(int j=1;j<=n;j++){
					if(con[i][j]==0)continue;
					if(ans[1][j]>s.cost){
						//2駅間の移動が出来た
						nextS.no=j;
						nextS.cost=s.cost;
						nextS.mode=1;
						ans[1][j]=s.cost;
						pq.push(nextS);
					}
				}
			}else{
				//無料チケットは使用済み
				if(ans[1][i]>nextS.cost){
					ans[1][i]=nextS.cost;
					pq.push(nextS);
				}
			}
		}
	}
	printf("%d\n",std::min(ans[1][n],ans[0][n]));
 }
 int main(){
	int n,m;
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)break;
		calc(n,m);
	}
 }








*0245 Time Sale
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0245
セール中のお店で効率よく買い物して回る問題。

何も考えず1ターンずつ進めていくメモ付きの幅優先探索で解いてみたら速度が出ませんでした。
なので探索中ある購入セットのサブセットが見つかったらそれは探索中次のターンに記憶しないという小手先のテクニックで10倍高速化しTop10入りを果たせました。




 #include<stdio.h>
 #include<set>
 #include<string.h>
 struct buyList{
	int buys;//どの商品を買ったか1ビット単位で管理
	int x,y;//今どこにいるか
	bool operator<(const buyList& b)const{
		if(x!=b.x)return x<b.x;
		if(y!=b.y)return y<b.y;
		return buys>b.buys;
	}
 };
 void setData(int w,int h){
	char map[22][22],c,t[2];
	std::set<buyList> memo[2];
	std::set<buyList>::iterator it;
	buyList b,nextB;
	b.buys=0;//何も買ってない状態からスタート
	for(int y=0;y<h;y++){
		for(int x=0;x<w;x++){
			scanf("%s%c",t,&c);
			map[y][x]=t[0];
			if(t[0]=='P'){
				b.x=x;
				b.y=y;
				map[y][x]='.';//床にしておく
			}else if(t[0]!='.'){
				map[y][x]-='0';//扱いやすいよう数字になおす
			}
		}
	}
	int gs[10],ds[10],ss[10],es[10];
	int m,g;
	scanf("%d",&m);
	memset(es,-1,sizeof(es));//値引きされない商品の値引き時間を-1に設定しておく
	memset(ds,0,sizeof(ds));//値引きされない商品は0円値引きとして扱う
	for(int i=0;i<m;i++){
		scanf("%d",&g);
		scanf("%d %d %d",&ds[g],&ss[g],&es[g]);
	}
	memo[0].insert(b);
	int oks[11];
	int dxs[]={1,0,-1,0};
	int dys[]={0,1,0,-1};
	int nx,ny;
	int now,next;
	memset(oks,false,sizeof(oks));	
	int stops[22][22];
	for(int i=0;i<=100;i++){
		for(int j=0;j<10;j++){
			oks[j]=(ss[j]<=i&&i<es[j])?(1<<j):0;//値引き中で売り切れてない商品の一覧
		}
		now =i&1;
		next=(i+1)&1;
		memo[next].clear();
		memset(stops,0,sizeof(stops));
		for(it=memo[now].begin();it!=memo[now].end();it++){
			b=(*it);
			//上下左右の商品を取れるだけ取る
			for(int j=0;j<4;j++){
				nx=b.x+dxs[j];
				ny=b.y+dys[j];
				if(nx<0||w<=nx||ny<0||h<=ny)continue;
				if(map[ny][nx]>9)continue;//上下左右が商品棚でない
				b.buys|=oks[map[ny][nx]];
			}
			//上下左右に移動
			for(int j=0;j<4;j++){
				nx=b.x+dxs[j];
				ny=b.y+dys[j];
				if(nx<0||w<=nx||ny<0||h<=ny)continue;
				if(map[ny][nx]!='.')continue;//上下左右が通路ではない
				int bs=(stops[ny][nx]&b.buys);
				if(bs==b.buys&&bs!=0)continue;//サブセットだった
				if(bs==stops[ny][nx])stops[ny][nx]=b.buys;//より大きい集合に直す
				b.y=ny;
				b.x=nx;
				memo[next].insert(b);
				b.x-=dxs[j];
				b.y-=dys[j];
			}
		}
	}
	int ans=0,sum;
	for(it=memo[next].begin();it!=memo[next].end();it++){
		int b1=(*it).buys;
		sum=0;
		for(int i=0;i<10;i++){
			if((b1&(1<<i))!=0){
				sum+=ds[i];
			}
		}
		ans=ans>sum?ans:sum;
	}
	printf("%d\n",ans);
 }
 int main(){
	int w,h;
	while(1){
		scanf("%d %d",&w,&h);
		if(w==0&&h==0)break;
		setData(w,h);
	}
 }