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

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

AOJ241~250 - (2012/07/12 (木) 14:55:19) の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);
+	}
+ }
+
+
+
+
+*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);
 	}
  }