後ろから考えてみる(タイルの色)

問題

$ N $ 枚のタイルがあり、最初はすべて白色で塗られています。

以下の操作を繰り返すことで、左から $ i $ 番目のタイルの色を文字 $ S_i$ （Rが赤、Bが青）にしたいです。

🔹連続する３つのタイルを赤色で塗り替える
🔹連続する３つのタイルを青色で塗り替える

目的を達成できる場合は“Yes”を、達成できない場合は“No”を出力して下さい。

[制約]
🔹$ 3 \leqq N \leqq 200000 $
🔹文字 $ S_i $ は R または B のいずれかである

解き方・ソースコード

この問題は、後ろから考えると容易に解くことができます。

まず最後の一手で塗り替えた３つのタイルの色は必ず同じになります。

つまり「連続する３つのタイルが同じ色である箇所」が存在しない場合、答えは”No”になります。

つぎに「連続する３つのタイルが同じ色である箇所」が存在する場合を考えます。

タイル $ p, p_+ 1, p + 2 $ が同じ色であるとき、以下の手順により目的を達成することができます。

🔹手順１：左から順に塗ることで、タイル $ p - 1 $ より左のタイルの色を確定させる。
🔹手順２：右から順に塗ることで、タイル $ p + 3 $ より右のタイルの色を確定させる。
🔹手順３：最後に、タイル $ p, p_+ 1, p + 2 $ を色 $ S_p $ で塗る。

以上のことから、連続する３つのタイルが同じ色である箇所があれば答えは“Yes”、そうでなければ答えは“No”となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#--------- 入力例1 ---------
N = 7           # タイルの枚数
S = 'BBRRRBB'   # タイルの色(Rが赤、Bが青)
#--------- 入力例2 ---------
#N = 7           # タイルの枚数
#S = 'BBRRBRB'   # タイルの色(Rが赤、Bが青)
#---------------------------
# 答えを求める
Answer = False
for i in range(0, N - 2):
    if S[i] == 'R' and S[i + 1] == 'R' and S[i + 2] == 'R':
        Answer = True
    if S[i] == 'B' and S[i + 1] == 'B' and S[i + 2] == 'B':
        Answer = True

# 出力
print('Yes' if Answer else 'No')

[実行結果（入力例１）]

Yes

以下のような操作を行えば目的が達成できます。

🔹タイル１，２，３を青色で塗る（青青青白白白白）
🔹タイル５，６，７を青色で塗る（青青青白青青青）
🔹タイル３，４，５を青色で塗る（青青赤赤赤青青）

[実行結果（入力例２）]

No

連続する３つのタイルが同じ色である箇所がありませんので、どのように操作しても目的のタイルの色にすることはできません。