ARC014 C - 魂の還る場所

問題原文

atcoder.jp

解法

とりあえず、消せる時は消してしまうのが最も得をしそうなのは明らか。

問題は消せない時。（例えば、 RG と詰めている時に、 B がきた時）

これは、 R、 G のうち片方が次きても消せなくなるのと同じなので、 R、G のうち「より早くくる方が消せるように」B を詰めるのが最適。

〜〜〜〜〜〜〜〜〜〜 ここまでが自分の解法 〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

もっと賢い人がたくさんいた。

1. RG とある時に B がきた場合、みるのは次の一手だけで大丈夫
   → 次が B なら 今の B は無視してよいし、 B でないなら R か G であるから

2. 答えは奇数個あるボールの種類
   １の応用で、RGとある時に B を入れた次のターンでは必ずボールを消せることがわかる。
   → 最大で RGB のような形にしかならないのなら、偶数個あるボールは全部消せる。

天才。

実装

それに比べて僕は、、、僕は、、、（まぁいいか）
アーリーリターンならぬアーリーコンティニューが僕はすきです。

from collections import deque
N = int(input())
S = input()

que = deque()
for i, s in enumerate(S):
    if len(que) == 0:
        que.append(s)
        continue

    if que[0] == s:
        que.popleft()
        continue

    if que[-1] == s:
        que.pop()
        continue

    if len(que) == 1:
        que.append(s)
        continue

    if i == N:
        que.append(s)
        continue

    for sj in S[i + 1:]:
        if sj == que[0]:
            que.append(s)
            break

        if sj == que[-1]:
            que.appendleft(s)
            break
    else:
        que.append(s)

print(len(que))

感想

かなりパズルチックで僕は好きです。
制約が なのがDPを疑ってしまってちょっと憎らしい。

推定diff1200とからしいけど、

atcoder.jp

とあんま変わらないような気もする（↑をやってたから解けたともいえる）