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

AOJ241~250 - (2012/07/13 (金) 17:13:49) の編集履歴(バックアップ)


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




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、1位ですね。
今のところも目算としては問題を解釈するデータ構造を根本から定義しなおして効率の良いグラフに縮約すれば好さそうです。



#include<stdio.h>
#include<set>
#include<string.h>
#include<map>
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));	
for(int i=0;i<=maxTime;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();
	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;//上下左右が通路ではない
			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);
}
}