「2181～2190」の編集履歴（バックアップ）一覧はこちら

「2181～2190」(2012/03/15 (木) 07:50:30) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*2190Angel Stairs
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2190
天使が音色を奏でながら階段を下りてくる問題。
動的計画法と幅優先探索の混合で最下位実行速度でアセプト。
なんか解けただけで満足してしまった問題。



 #include<stdio.h>
 #include<iostream>
 #include<string>
 #include<string.h>
 #include<map>
 #include<vector>
 std::map<std::string,int> toNo;
 int mod=12;
 void set(){
	toNo["C"] =0;
	toNo["C#"]=1;
	toNo["D"] =2;
	toNo["D#"]=3;
	toNo["E"] =4;
	toNo["F"] =5;
	toNo["F#"]=6;
	toNo["G"] =7;
	toNo["G#"]=8;
	toNo["A"] =9;
	toNo["A#"]=10;
	toNo["B"] =11;
 }
 int memo[2][50002];
 int n,m;
 void calc(){
	std::string str;
	std::vector<int> dan[12];
	for(int i=0;i<n;i++){
		std::cin>>str;
		dan[toNo[str]].push_back(i+1);
	}
	int now,p,size,oto,nextTurn,nowTurn,up=1;
	bool nextOK,allBad=false;
	memset(memo,-1,sizeof(memo));
	memo[0][0]=0;
	for(int i=0;i<m;i++){
		std::cin>>str;
		if(allBad==true) continue;
		up+=2;
		nextTurn=(i+1)&1;
		nowTurn =i&1;
		nextOK=false;	
		//一段降りる
		now=toNo[str];
		oto=now;
		size=dan[oto].size();
		for(int j=0;j<size;j++){
			p=dan[oto][j];
			if(p>up) break;
			if(p-1>=0 && memo[nowTurn][p-1]==i){
				memo[nextTurn][p]=i+1;
				nextOK=true;
			}
		}
		//2段降りる
		oto=(now+11)%mod;
		size=dan[oto].size();
		for(int j=0;j<size;j++){
			p=dan[oto][j];
			if(p>up)break;
			if(p-2>=0 && memo[nowTurn][p-2]==i){
				memo[nextTurn][p]=i+1;
				nextOK=true;
			}
		}
		//一段上がる
		oto=(now+1)%mod;
		size=dan[oto].size();
		for(int j=0;j<size;j++){
			p=dan[oto][j];
			if(p>up) break;
			if(p+1<n+1 && memo[nowTurn][p+1]==i){
				memo[nextTurn][p]=i+1;
				nextOK=true;
			}
		}
		if(nextOK==false){
			allBad=true;
		}
		//for(int j=1;j<=n;j++)printf("%d ",memo[nextTurn][j]);
		//printf("\n");
	}
	printf("%s\n",memo[nextTurn][n]>=m||memo[nextTurn][n-1]>=m?"Yes":"No");
 }
 int main(){
	set();
	int r;
	scanf("%d",&r);
	while(r--){
		scanf("%d %d",&n,&m);
		calc();
	}
 }

*2190Angel Stairs
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2190
天使が音色を奏でながら階段を下りてくる問題。
動的計画法と幅優先探索の混合で最下位実行速度でアセプト。
なんか解けただけで満足してしまった問題。
動的計画法で、ｎ個目の音を鳴らす時、ｎ-1個目までの音を鳴らしおえた段以外はすべて無視するということで高速化を図ってます。



 #include<stdio.h>
 #include<iostream>
 #include<string>
 #include<string.h>
 #include<map>
 #include<vector>
 std::map<std::string,int> toNo;
 int mod=12;
 void set(){
	toNo["C"] =0;
	toNo["C#"]=1;
	toNo["D"] =2;
	toNo["D#"]=3;
	toNo["E"] =4;
	toNo["F"] =5;
	toNo["F#"]=6;
	toNo["G"] =7;
	toNo["G#"]=8;
	toNo["A"] =9;
	toNo["A#"]=10;
	toNo["B"] =11;
 }
 int memo[2][50002];
 int n,m;
 void calc(){
	std::string str;
	std::vector<int> dan[12];
	for(int i=0;i<n;i++){
		std::cin>>str;
		dan[toNo[str]].push_back(i+1);
	}
	int now,p,size,oto,nextTurn,nowTurn,up=1;
	bool nextOK,allBad=false;
	memset(memo,-1,sizeof(memo));
	memo[0][0]=0;
	for(int i=0;i<m;i++){
		std::cin>>str;
		if(allBad==true) continue;
		up+=2;
		nextTurn=(i+1)&1;
		nowTurn =i&1;
		nextOK=false;	
		//一段降りる
		now=toNo[str];
		oto=now;
		size=dan[oto].size();
		for(int j=0;j<size;j++){
			p=dan[oto][j];
			if(p>up) break;
			if(p-1>=0 && memo[nowTurn][p-1]==i){
				memo[nextTurn][p]=i+1;
				nextOK=true;
			}
		}
		//2段降りる
		oto=(now+11)%mod;
		size=dan[oto].size();
		for(int j=0;j<size;j++){
			p=dan[oto][j];
			if(p>up)break;
			if(p-2>=0 && memo[nowTurn][p-2]==i){
				memo[nextTurn][p]=i+1;
				nextOK=true;
			}
		}
		//一段上がる
		oto=(now+1)%mod;
		size=dan[oto].size();
		for(int j=0;j<size;j++){
			p=dan[oto][j];
			if(p>up) break;
			if(p+1<n+1 && memo[nowTurn][p+1]==i){
				memo[nextTurn][p]=i+1;
				nextOK=true;
			}
		}
		if(nextOK==false){
			allBad=true;
		}
		//for(int j=1;j<=n;j++)printf("%d ",memo[nextTurn][j]);
		//printf("\n");
	}
	printf("%s\n",memo[nextTurn][n]>=m||memo[nextTurn][n-1]>=m?"Yes":"No");
 }
 int main(){
	set();
	int r;
	scanf("%d",&r);
	while(r--){
		scanf("%d %d",&n,&m);
		calc();
	}
 }