D - Writing a Numeral

[hxrxchang]

https://atcoder.jp/contests/abc298/tasks/abc298_d

問題概要

初期値 "1" の文字列 Sがある。

• Q[0] == 1のときSの末尾にQ[1]を追加。
• Q[0] == 2のときSの先頭の文字を削除。
• Q[0] == 3のとき int(S) % MOD を出力

せよ。

解き方

問題通りSを文字列で管理して、出力時にintにする方法では、Qが最大 10 ** 5 のため

• 文字追加・削除がO(N)
• int(S) が O(N)

のため間に合わない。

よって S[0] == 1、S[0] == 2 のときに答えをO(1) で変更する方法を考える。 答え(以後 ans)の初期値は 1。

Q[0] == 1

ansを10倍してS[1] を足せばいい

Q[0] == 2

先頭の数字を削除するために、"今の先頭" をqueで管理。 削除するときにqueの先頭を取り出して、ans を 取り出した要素 * pow(10, 桁数 - 1, MOD) で更新する 例: 321 を 21 にするには 321 - 3 * pow(10, 2(桁数は3なのでマイナス1), MOD) でよい。

Pythonのpowは繰り返し二乗法で、第三引数にmodを取れるのが便利

from collections import deque
MOD = 998244353

N = int(input())
que = deque()
ans = 1
que.append(1)

for _ in range(N):
    Q = list(map(int, input().split()))
    if Q[0] == 1:
        que.append(Q[1])
        ans = (ans * 10 + Q[1]) % MOD
    elif Q[0] == 2:
        keta = len(que)
        top = que.popleft()
        ans -= top * pow(10, keta - 1, MOD)
        ans %= MOD
    elif Q[0] == 3:
        print(ans)