CPSCO2019 Session3 D - Decode RGB Sequence (400 点設定)

最初は文字列 を文字列 にできるかを問うつもりだった。てんぷら君のおかげで、 を真っ白にすることで、シンプルな問題になった！

• 問題へのリンク

問題概要

マスがあって最初はすべて白く塗られている。ここに "RGB" のスタンプを押していく。スタンプを押すと次にようになる。

• 連続する 3 マスが「R」「G」「B」に上塗りされる

スタンプは好きな回数だけ好きな場所に好きな順序で押すことができる。最終結果を文字列 ('R', 'G', 'B' のみからなる) の状態にすることは可能か？

制約

• 

解法

まずこの操作が「スタンプが押された箇所の過去の履歴を消して上書きする」というタイプの操作であることに注目しよう。そのような操作をする問題では「後ろから見る」というのが案外有効だったりする。

今回、文字列 が作れるとしたとき、 の最後に押された箇所には "RGB" とスタンプされているはずである。よって

• が "RGB" を含まない場合は不可能

ということが直ちに言える。そして操作列を逆から見ると、

「すでに白色でなくなっている箇所は変更せず、白色の部分にはスタンプの該当文字が押される」

という風に表現できることがわかる。

解法(1)：ちょっと大変なシミュレーション

上に述べたことを実際に行う解法が考えられる。つまり、 の中のそれぞれの "RGB" に対して

• 各 "RGB" から左側へと "R" や "RG" で区間ごとに区切っていく
• 各 "RGB" から右側へと "B" や "GB" で区間ごとに区切っていく

そうしたときに、

• 左端と右端はすべてくまなく切り取られる
• それぞれの "RGB" と "RGB" との間には何も残らないか、"G" のみが残る

というふうになれば OK。

解法 (2)：簡単な特徴づけ

実はもっと簡単な特徴づけもできる！！！実は以下が必要十分！！！

---

• 左端は 'R'
• 右端は 'B'
• "RB" と "GG" を含まない

---

まず、これらの条件を違反していたら不可能であることは自明。逆にこれらを満たすとき、可能であることを言おう。

まず "RGB" が存在しないとダメだけど、"RGB" が存在することは次のように言える。

• の中で最も左側にある "B" を考える
• "RB" は含まないので、"B" の左隣は "G" である ("B" ではない)
• "GG" は含まないので、その "G" の左隣は "R" である

よって、 が "RGB" を必ず含むことがわかった。また、次のように操作を復元できるので大丈夫。

• 先頭から最初の "B" までの区間は、"GG" が存在しないことから、"R" と "RG" で区切れることになるので OK
  • 先頭が "G" でないことに注意
• 最初の "B" のその次の "B" を考えると、同様にその "B" も "RGB" の一部になっていることが言える。そして最初の "B" とその次の "B" との間の区間については、次のことが言えるので OK
  • 先頭が "G" である可能性はある (問題ない)
  • それ以外は "R" と "RG" のみで区切ることができる
• 以下同様にできる。

以上から、わかりやすい特徴づけが得られたので容易に判定できる。計算量は 。

コード

#include <iostream>
#include <string>
using namespace std;

bool solve(int N, const string &S) {
    if (S[0] != 'R') return false;
    if (S.back() != 'B') return false;

    for (int i = 0; i < N-1; ++i) {
        if (S[i] == 'R' && S[i+1] == 'B') return false;
        if (S[i] == 'G' && S[i+1] == 'G') return false;
    }
    return true;
}

int main() {
    int N;
    string S;
    cin >> N >> S;

    if (solve(N, S)) cout << "Yes" << endl;
    else cout << "No" << endl;
}