AOJ 2190:Angel Stairs

問題

Angel Stairs | Aizu Online Judge

解法

後ろからたどっていけば良いです。
例えば, ひとつ目の入力例を見ていきましょう。

C E D# F G A
C E F G

まずそれぞれの配列を逆さまにします。

A G F D# E C
G F E C

まず G を作る必要があります。スタートが A だとどのように半音ずらしても G にはならないので最初(実際には最後)に踏む階段は A ではないです。
一方で, スタートが G の場合, G を踏むときに一段降りてきたと考えれば G という音を出せます。よって, G の前に踏んでいた階段は G の一つ上である F であるとわかります。
次に作る必要のある音は F です。これも先ほどと同様に一段降りてきたと考えれば良いので F の前に踏んでいた階段は D# です。
次に作る必要のある音は E です。今度は一段とばしで降りてきたと考えると E の音が出るので, D# の前に踏んでいた階段は C です。で, C を出すために一段降りて雲に着く, というわけです。

これを上手く実装すれば良いです。

const int MAXN = 50040;
int T[MAXN], S[MAXN];

bool check(int start, int n, int m) {
    int now = start;
    for (int i = 0; i < m; i++) {
        if (now > n-1) return false;
        int tar = S[i];
        bool ok = false;
        for (int j = -1; j <= 1; j++) {
            int next = (T[now]+j + 12) % 12;
            if (tar == next) {
                ok = true;
                now += j;
                if (j >= 0) now++;
                break;
            }
        }
        if (now < 0) return false;
        if (!ok) return false;
    }
    if (now == n) return true;
    else return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int test;
    cin >> test;
    map<string, int> oto;
    oto["C"] = 0;
    oto["C#"] = 1;
    oto["D"] = 2;
    oto["D#"] = 3;
    oto["E"] = 4;
    oto["F"] = 5;
    oto["F#"] = 6;
    oto["G"] = 7;
    oto["G#"] = 8;
    oto["A"] = 9;
    oto["A#"] = 10;
    oto["B"] = 11;
    while (test--) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            T[i] = oto[s];
        }
        for (int i = 0; i < m; i++) {
            string s;
            cin >> s;
            S[i] = oto[s];
        }
        reverse(S, S+m);
        reverse(T, T+n);
        if (check(0, n, m) || check(1, n, m)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}