yukicoder No.154 市バス

ものすごく久しぶりに記事を書いている気がする…

問題

No.154 市バス - yukicoder

解法

この問題では,

• G と R のペアが存在するかどうか
• 存在するとしたら, そのペアについて, 対応する W が少なくとも 1 つ存在するかどうか

というのが問題です。

どちらも stack でカッコが valid かどうかチェックするのと似ています。
s を反転させて, R を '(', G を ')' としたときに, 構成されるカッコ列が valid なものかを確かめます。これは, (今までにあった 'R' の数) - (今までにあった 'G' の数) が 常に 0 以上であり, 最後には 0 になっていれば OK です。ただ, これだけじゃなくて, 「ひとつも 'RG' というペアが出来ていないときに　'W' が来るのは NG」というルールもあります(一つでも 'RG' というペアが出来た後だったら 'W' はその 'RG' とペアになっていると考えれば整合が取れるが, そうでない場合は その 'W' とペアになるものがないから)。

後者のほうですが, すでに前者をチェックしたことによって, 各 'G' について対応する 'R' があることは分かっているので, 後は 各 'G' に対応する 'W' が存在することを確かめれば良いです。
これもさっきと同様で反転させていない s について, 'W' を '(', 'G' を ')' とみなして valid かどうか確かめるような感じになります。ただ, 今回の場合は一つの 'G' に対応する 'W' は複数あっても良いので, 最後に (今までにあった 'W' の数) - (今までにあった 'G' の数) が 0 でなくても大丈夫です。

bool solve(string s) {
    reverse(s.begin(), s.end());
    int n = s.size();
    if (n < 3) return false;
    int cnt = 0;
    bool flag = false;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') cnt++;
        else if (s[i] == 'G') {
            if (--cnt < 0) return false;
            flag = true;
        } else {
            if (!flag) return false;
        }
    }
    if (cnt) return false;
    reverse(s.begin(), s.end());
    cnt = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'W') cnt++;
        else if (s[i] == 'G') {
            if (--cnt < 0) return false;
        }
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        if (solve(s)) cout << "possible" << endl;
        else cout << "impossible" << endl;
    }
    return 0;
}

1 年くらい前にやったときあきらめた問題を解けたのでとてもうれしい。