AOJ 2190 : Angel Stairs

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

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

文字列だと扱いにくいのでCからBまでの音を数字の0から11として考える
今いる場所が持つ音をi (0 <= i <= 11)とすると、
iからi,i+1,i-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;
}