Problem:


Problem F: 天使の階段

なつめの住んでいる街の上に浮かんでいる雲には、天使が住んでいる。その天使はなつめと同じくねこ好きで、しばしばねこと遊びに地上に降りてくる。地上に降りるために、天使は雲から地上へ繋がる長い長い階段を作った。しかし、毎回毎回ただ降りていくだけではつまらないと思った天使は、階段に細工をして、段を踏むと音が出るようにした。これを使って、音楽を奏でながら降りていくのだ。

音楽は12種類の音を使って奏でるものである。今回、音のオクターブは無視することにして、 C, C#, D, D#, E, F, F#, G, G#, A, A#, B の12種類のみを考える。隣りあう音同士の差を半音と呼ぶ。たとえば、Cを半音上げるとC#、C#を半音上げるとDとなる。逆に、Gを半音下げるとF#、 F#を半音下げるとFとなる。なお、Eを半音上げるとF、Bを半音上げるとCになることに注意してほしい。

階段から音が出る仕組みは次のようになっている。まず、階段は空中に浮かぶ n 枚の白い板からなっている。雲から数えて 1 ~ n 段目の板には、それぞれに12音のどれかが割り振られている。これを Ti (i = 1 ... n) と書くことにする。また簡単のために、雲は0段目、地上は n+1 段目と考える (ただしこれらには音階は割り当てられていない) 。天使が k (k = 0 ... n) 段目にいるとき、次はk-1, k+1, k+2 段のうち存在するもののどれかに行くことができる。ただし、n+1 段目 (地上) に降りた後は動くことはできず、0段目 (雲) を離れた後はそこに戻ることはできない。それぞれの動き方をしたとき、次のようなルールで音が鳴る。

k+1 段目に降りた

    Tk+1 の音が鳴る。

k+2 段目に降りた

    Tk+2 を半音上げた音が鳴る。

k-1 段目に戻った

    Tk-1 を半音下げた音が鳴る。

階段の情報 T1 ... Tn と、天使が奏でたい曲 S1 ... Sm が与えられる。このとき、奏でたい曲の前、途中、後で別の音を鳴らしてはならない。天使がこの曲を奏でて雲から地上へ降りられるかどうか判定せよ。

Input

入力の1行目には、階段の段数 n と天使が奏でたい曲の長さ m が与えられる。2行目は階段の情報であり、T1, T2, ..., Tn がこの順で与えられる。3行目は天使が奏でたい曲であり、S1, S2, ..., Sm がこの順で与えられる。これらは全て1つの空白文字で区切られており、1 <= n, m <= 50000を満たす。

Output

天使が与えられた曲を奏でながら地上に降りられるなら"Yes"、そうでなければ"No"を1行に出力せよ。

Notes on Submission

上記形式で複数のデータセットが与えられます。入力データの 1 行目にデータセットの数が与えられます。各データセットに対する出力を上記形式で順番に出力するプログラムを作成して下さい。

Sample Input

4
6 4
C E D# F G A
C E F G
6 4
C E D# F G A
C D# F G
3 6
C D D
D# B D B D# C#
8 8
C B B B B B F F
C B B B B B B B

Output for the Sample Input

Yes
No
Yes
No



Sample input:
4
6 4
C E D# F G A
C E F G
6 4
C E D# F G A
C D# F G
3 6
C D D
D# B D B D# C#
8 8
C B B B B B F F
C B B B B B B B


Sample output:
Yes
No
Yes
No

Submission status: Memory Limit Exceeded

Solution code:
def notetonum(notestr):
    numlist=[]
    nn=["C","C#","D","D#","E","F","F#","G","G#","A","A#","B"]
    for c in notestr:
        numlist.append(nn.index(c))
    return numlist


Q=int(raw_input())
for q in range(Q):
    [n,m]=[int(x) for x in raw_input().split()]
    stairlist=notetonum(raw_input().split())
    songlist=notetonum(raw_input().split())
    dp=[[0 for x in range(n)] for y in range(m)]
    if songlist[0]==stairlist[0]:
        dp[0][0]=1
    if songlist[0]==(stairlist[1]+1)%12:
        dp[0][1]=1
    for i in range(m-1):
        for j in range(0,n):
            if j<n-1 and dp[i][j] and songlist[i+1]==stairlist[j+1]:
                dp[i+1][j+1]=1
            if j<n-2 and dp[i][j] and songlist[i+1]==(stairlist[j+2]+1)%12:
                dp[i+1][j+2]=1
            if j>0 and dp[i][j] and songlist[i+1]==(stairlist[j-1]-1)%12:
                dp[i+1][j-1]=1
    print dp
    if dp[m-1][n-1] or dp[m-1][n-2]:
        print "YES"
    else:
        print "NO"

Submission status: Accepted

Solution code:
dic = {"C":0, "C#":1, "D":2, "D#":3,
       "E":4, "F":5, "F#":6, "G":7,
       "G#":8, "A":9, "A#":10, "B":11}
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  t_lst = [-100] + list(map(lambda x:dic[x],input().split()))
  s_lst = list(map(lambda x:dic[x],input().split()))
  s_lst.reverse()
  
  def search(stack):
    t_index, s_index = stack.pop()
    if s_index == m: return t_index == 0
    if t_index <= 0 or t_index > n: return False
    base = t_lst[t_index]
    proc = s_lst[s_index]
    diff = (proc - base) % 12
    if diff == 1  :stack.append((t_index - 2, s_index + 1))
    if diff == 0  :stack.append((t_index - 1, s_index + 1))
    if diff == 11 :stack.append((t_index + 1, s_index + 1))
    return False
  stack = [(n, 0), (n - 1, 0)]
  while stack:
    if search(stack):
      print("Yes")
      break
  else:
    print("No")

Submission status: Runtime Error

Solution code:
dic = {"C":0, "C#":1, "D":2, "D#":3,
       "E":4, "F":5, "F#":6, "G":7,
       "G#":8, "A":9, "A#":10, "B":11}
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  t_lst = [-100] + list(map(lambda x:dic[x],input().split()))
  s_lst = list(map(lambda x:dic[x],input().split()))
  s_lst.reverse()
  
  def search(t_index, s_index):
    if s_index == m: return t_index == 0
    if t_index <= 0 or t_index > n: return False
    base = t_lst[t_index]
    proc = s_lst[s_index]
    diff = (proc - base) % 12
    if diff == 1  and search(t_index - 2, s_index + 1) or\
       diff == 0  and search(t_index - 1, s_index + 1) or\
       diff == 11 and search(t_index + 1, s_index + 1): return True
    return False
  
  print("Yes" if search(n, 0) or search(n - 1, 0) else "No")

Submission status: Runtime Error

Solution code:

def notetonum(notestr):
    numlist=[]
    nn=["C","C#","D","D#","E","F","F#","G","G#","A","A#","B"]
    for c in notestr:
        numlist.append(nn.index(c))
    return numlist


Q=int(raw_input())
for q in range(Q):
    [n,m]=[int(x) for x in raw_input().split()]
    stairlist=notetonum(raw_input().split())
    songlist=notetonum(raw_input().split())
    #dp=[[0 for x in range(n)] for y in range(m)]
    stateold=[0 for x in range(n)]
    statenew=[0 for x in range(n)]
    isoneold=[]
    isonenew=[]
    if songlist[0]==stairlist[0]:
        stateold[0]=1
        isoneold.append(0)
    if songlist[0]==(stairlist[1]+1)%12:
        statenew[1]=1
        isoneold.append(1)
    for i in range(m-1):
        isonenew=[]
        for j in isoneold:
            if j<n-1 and songlist[i+1]==stairlist[j+1]:
                statenew[j+1]=1
                isonenew.append(j+1)
            if j<n-2 and songlist[i+1]==(stairlist[j+2]+1)%12:
                statenew[j+2]=1
                isonenew.append(j+2)
            if j>0 and songlist[i+1]==(stairlist[j-1]-1)%12:
                statenew[j-1]=1
                isonenew.append(j-1)
            stateold=statenew[:]
            isoneold=set(isonenew)
    if statenew[n-1] or statenew[n-2]:
        print "YES"
    else:
        print "NO"