第二回 PAST G - ストリング・クエリ

問題原文

atcoder.jp

問題要旨

文字列 に対して、 回のクエリを実行せよ。
最初 は空文字列である。 クエリには以下の２種類ある。
1. の末尾に英子文字 を つ追加する。
2. の先頭から 文字削除する。この操作で、 a, b, ... z がそれぞれ何文字削除されたかを求め、それぞれの削除個数の二乗の和を出力する。

• 
• 
• 

解法

愚直にやってはダメなので、うまく状態を管理できないかを考える。
(文字種, 何文字続くか) という形で をもてば追加も削除も楽に管理できる。

実装

削除の形はABCとかでたまにみますね。
先頭削除は deque を使うべし。

from collections import deque
Q = int(input())
S = deque([])
 
for q in range(Q):
    query = input().split()
    if query[0] == '1':
        c, x = query[1], int(query[2])
        S.append([c, x])
 
    elif query[0] == '2':
        d = int(query[1])
        cnt = {chr(ord('a') + i): 0 for i in range(26)}
        d = int(query[1])
 
        while d and S:
            c, x = S[0]
            if x <= d:
                cnt[c] += x
                d -= x
                S.popleft()
            else:
                S[0][1] -= d
                cnt[c] += d
                d = 0
 
        ans = sum([v ** 2 for v in cnt.values()])
        print(ans)

感想

緑下diffのABC-D感があるなぁと思いました。