[PYTHON] AtCoder ARC014 C-The place where the soul returns Look-ahead simulation

https://atcoder.jp/contests/arc014/tasks/arc014_3 Although it is written as look-ahead, it is just one step ahead.

The bottom line is that the queue cannot have more than one character r, g, b if it is optimally packed. In other words, all even characters can be erased, so the answer is the sum of% 2 for each of r, g, and b.

Overview

--There is a queue where you can enter characters from both directions. (Hereafter, it is assumed that it can be inserted from the left and right) ――The character strings consisting of the letters R, G, and B are packed in a fixed order. You can put it on either the left or right side. Must be packed and must not be skipped. ――This character disappears when two are adjacent --Please answer the minimum of the last remaining letters

the term

--addL: Add a letter to the left --addR: Add a letter to the right --L, R: One character on the left and right in the queue --cur, next: The character to be added now and the character to be added next (that is, one character look-ahead)

Way of thinking

Consider the packing order as follows, you can arrange each character so that only one character remains in this queue.

--If the queue has less than 2 characters, add it appropriately (for example, addL (cur)) --If you can erase it with addL or addR, cur will do that and erase the character --The fact that it cannot be erased is a character that is not L or R, but if cur == next, add it appropriately (in this case, if you process addL, addL, that character can be erased without fail). --If cur! = next, next always matches either L or R. Therefore, put cur in the opposite way. In this case, you can always erase it by putting next (as cur for the next turn) and vice versa.

Implementation

You can simply simulate the above. However,

--Characters can be arranged in the queue so that each character remains at most one character. (That is, it can be arranged so that no more than two characters are left) --From the subject, it is clear that if each character is odd, the rest of that character will not be zero. (Because you can only erase 2 characters at a time)

Given that

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

It may be. There is a lot of waste in order to display the solution in an easy-to-understand manner

#If you comment out of print, the solution will come out.
from collections import deque
n, s = int(input()), input()
q = deque([])
step = [0]
###Queue simulation from here
def addL(ch): #Try to put it on the left. If it is the same color, erase it
    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): #Try to put it on the right. If it is the same color, erase it
    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
###Queue simulation so far
for i in range(min(2, n)): # 1,Insert the second character appropriately
    addL(s[i])
#Put the sentinel at the end of the string
n += 1
s += "_"
for i in range(2, n - 1):
    curCh, nCh = s[i : i+2]
    if curCh == "_": break #Guard
    if len(q) < 2: #Appropriate when the current queue is 0 or 1 character(Anyway, save 2 letters)
        addL(s[i])
        continue
    qL, qR = q[0], q[-1]
    if qL == curCh:#If you can erase it on the left, erase it on the left
        addL(curCh)
        continue
    if qR == curCh: #If you can erase it with the right child, turn it to the right
        addR(curCh)
        continue
    #In this case, the current character is qL,Something different from qR
    #But next(=nch)But now(=curChar)If it is the same as, it can be erased next time, so anything is fine(Try to put it on the left)
    if curCh == nCh:
        addL(curCh)
        continue
    #If you can't do that, nCh(What to put next)Can be erased with qL or qR. So, put the current characters in reverse
    #Then nCh can definitely be erased(Excludes sentinels)
    if nCh == qL:
        addR(curCh)
        continue
    if nCh == qR:
        addL(curCh)
        continue
    addL(curCh) #Anything is fine if you can't erase it with the last letter
print(len(q))

https://atcoder.jp/contests/arc014/submissions/19185809