読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 2190 : Angel Stairs

問題リンク : Angel Stairs | Aizu Online Judge

解法:
天使が奏でたい曲を最初からみていくのではなく最後からみていく
最初から見ていくと移動先が複数考えられるが、後ろから見ていくと移動先は1つに定まる

文字列だと扱いにくいのでCからBまでの音を数字の0から11として考える
今いる場所が持つ音をi (0 <= i <= 11)とすると、
iからi,i+1,i-1に音を変える事ができる
これらの内今奏でたい音と一致するものは1つだけである(i,i+1,i-1はそれぞれ異なるため)
そのため移動先は一意に定まる
あとはその通り曲を逆順で奏でていきスタートにもどれるかどうか確認すれば良い

Bを半音あげるとCに、Cを半音さげるとBになる事に注意

コード:

map<string,int> getIndex;
int t,s;
bool found;
int T[MAX],S[MAX];
string type[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
int dc[] = {+0,+1,-1};
int dx[] = {-1,-2,+1};

void dfs(int cur_t,int cur_s)
{
  if(cur_s < 0)
    {
      if(cur_t == -1)found = true;
      return;
    }

  rep(i,3)
    {
      int music = (T[cur_t] + dc[i] + 12)%12;
      if(t <= cur_t+dx[i])continue;

      if(music == S[cur_s])dfs(cur_t+dx[i],cur_s-1);
    }
}

bool compute()
{
  found = false;
  dfs(t-1,s-1);
  if(!found)dfs(t-2,s-1);
  return found;
}

int main()
{
  rep(i,12)getIndex[type[i]] = i;
  int N;
  while(cin >> N)
    {
      while(N--)
	{

	  cin >> t >> s;
	  string input;
	  rep(i,t)
	    {
	      cin >> input;
	      T[i] = getIndex[input];
	    }
	  rep(i,s)
	    {
	      cin >> input;
	      S[i] = getIndex[input];
	    }
	  cout << (compute()?"Yes":"No") << endl;
	}
    }
  return 0;
}