ABC477Dを解いた【クエリ逆順処理】

筆者はレート800前後の茶～緑コーダ

ABC477のD問題を解いていく

実装コード

クエリを逆順に処理し、更新対象の位置を集合で管理しながら、各位置の最終的な文字を一度ずつ確定する。

• N, Q を受け取り、すべてのクエリを q_lst に保存する。種類 1 のクエリでは T[x] ^= 1 で状態を反転させ、全クエリ処理後の状態を求める
• T[i] が 0 の位置を集合 pos に入れる。pos は、文字が未確定で、現在の状態では文字の更新対象になる位置を管理する
• 確定済みかを表す flg を False、答えの配列 ans を初期文字の 'a' で初期化する
• reversed(q_lst) でクエリを後ろからたどる。種類 1 なら T[x] を反転して元の状態に戻し、未確定の位置だけ pos への追加・削除を行う
• 種類 2 なら、pos 内の各位置の文字を x に確定し、flg[i] を True にする。逆順では最初に出会う更新が、その位置への最後の更新になる
• 確定した位置は今後扱わないため pos.clear() で集合を空にする。各位置の文字を確定する処理は高々一度なので、全体を O(N + Q) の計算量で処理できる
• 一度も文字が更新されない位置には 'a' を残し、最後に ans[1:] を連結して出力する

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, Q = rLI()
    q_lst = []
    T = [0] * (N + 1)
    for _ in range(Q):
        t, x = rLS()
        t = int(t)
        if t == 1:
            x = int(x)
            T[x] ^= 1
        q_lst.append((t, x))

    pos = {i for i in range(1, N + 1) if not T[i]}
    flg = [False] * (N + 1)
    ans = ['a'] * (N + 1)
    for t, x in reversed(q_lst):
        if t == 1:
            T[x] ^= 1
            if not flg[x]:
                if not T[x]:
                    pos.add(x)
                else:
                    pos.discard(x)
        else:
            for i in pos:
                ans[i] = x
                flg[i] = True
            pos.clear()

    print(''.join(ans[1:]))

if __name__ == '__main__':
    main()

感想

クエリを逆順に見ると、各位置への最後の更新から文字を確定できるのがポイントだった。
確定した位置を集合から取り除くことで、同じ位置を何度も更新せずに済むようだ。