AtCoder ARC014 C - 魂の還る場所 先読みしたシミュレーション

https://atcoder.jp/contests/arc014/tasks/arc014_3
先読みと書いていますが、単に１手先を読むだけです。

結論は、キューには最適に詰めていった場合r,g,bを2文字以上存在できません。つまり、偶数個の文字はすべて消しきれるため、r,g,bそれぞれについて%2した和が答えになります。

概要

• 双方向から文字を入れられるキューがあります。(以下、左右から入れられるとします)
• あるR,G,Bという文字からなる文字列を決められた順番に詰めていきます。左右どちらに入れてもよいです。必ず詰めなければならず、スキップしてはいけません。
• この文字は２つ隣接すると消えます
• 最後に残る文字の最小を答えなさい

用語

• addL: 左に字を入れる
• addR: 右に字を入れる
• L,R: キューに入っている左と右の1文字
• cur, next: それぞれ今追加しようとする文字、と次に追加する文字(つまり1文字先読み)

考え方

以下のようにしてこのキューには各文字が最大でも1文字までしか残らないように配置ができるような詰める順番を考えます。

• キューの文字が2文字に満たない場合、適当に追加する(例えばaddL(cur)する)
• addLかaddRをして消せる場合、curはその処理を行い文字を消す
• これで消せていないということはL,Rではない文字であるが、もし、cur == nextなら適当に追加する(この場合、addL, addLと処理すれば確実にその文字は消せるため)
• cur != nextの場合、nextは必ずLかRのどちらかと一致する。そのため、curをそれとは逆に入れる。この場合、nextを(次のターンのcurとして)その逆に入れれば必ず消せる。

実装

上記を愚直にシミュレーションすればよい。ただし、

• キューに文字は各文字が最大でも1文字までしか残らないように配置ができる。(つまり、２文字以上残さないように配置できる)
• 題意から、各文字が奇数である場合、その文字の残りが0にならないことは明らかである。(2文字ずつしか消せないのだから)

ことを考えると、

n,s=input(),input()
print(s.count("R")%2+s.count("G")%2+s.count("B")%2)

でもよい。
解をわかりやすく表示するために、ものすごく無駄が多いです

# printのcomment outをすると解法が出る
from collections import deque
n, s = int(input()), input()
q = deque([])
step = [0]
### ここからキューのシミュレーション
def addL(ch): # 左に入れようとする。同じ色なら消す
    step[0] += 1
    #print("step[", step[0], "]: Left  ", ch, "current :", q)
    if len(q) == 0:
        q.append(ch)
        return
    nch = q.popleft()
    if nch != ch:
        q.appendleft(nch)
        q.appendleft(ch)
        return
def addR(ch): # 右に入れようとする。同じ色なら消す
    step[0] += 1
    #print("step[", step[0], "]: Right ", ch, "current :", q)
    if len(q) == 0:
        q.append(ch)
        return
    nch = q.pop()
    if nch != ch:
        q.append(nch)
        q.append(ch)
        return
### ここまでキューのシミュレーション
for i in range(min(2, n)): # 1,2文字目は適当に突っ込む
    addL(s[i])
# 文字列の最後に番兵を突っ込んでおく
n += 1
s += "_"
for i in range(2, n - 1):
    curCh, nCh = s[i : i+2]
    if curCh == "_": break # 番兵
    if len(q) < 2: # 今のキューが0 or 1文字の時は適当でいい(とにかく２文字貯める)
        addL(s[i])
        continue
    qL, qR = q[0], q[-1]
    if qL == curCh:# 左で消せるなら左で消す
        addL(curCh)
        continue
    if qR == curCh: # 右の子で消せるなら右に
        addR(curCh)
        continue
    # この場合、今の文字は、qL, qRと異なる何か
    # だが、次(=nch)が、今(=curChar)と同じなら、どうせ次で消せるのでなんでもいい(左に入れてみる)
    if curCh == nCh:
        addL(curCh)
        continue
    # それができない場合は、nCh(さらに次に入れるもの)は絶対にqLかqRで消せる。だから、今の文字は逆に入れる
    # そうすると、nChは絶対に消せる(番兵は除く)
    if nCh == qL:
        addR(curCh)
        continue
    if nCh == qR:
        addL(curCh)
        continue
    addL(curCh) # 最後の文字で消せないときはなんでもいい
print(len(q))