「2181～2190」の編集履歴（バックアップ）一覧に戻る

2181～2190 - (2012/03/15 (木) 07:50:30) のソース

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