概要

命令列 \(S\) は更新されながら、質問ごとに「ロボットが最初の状態から \(S\) を実行したときのスコア」を求めます。
制約に \(KQ \leq 2 \times 10^7\) があるため、各質問ごとに命令列全体をシミュレーションできます。

考察

質問操作 2 のたびに、ロボットは毎回以下の初期状態から実行を始めます。

• 部屋 \(1\) にいる
• スコアは \(0\)
• すべての宝は未回収

そのため、質問ごとに命令列 \(S\) を先頭から順に見てシミュレーションすれば答えを求められます。

一見すると、質問のたびに「各部屋の宝が回収済みか」を表す配列を毎回初期化したくなります。
しかし、部屋数 \(N\) は最大 \(2 \times 10^5\) なので、質問のたびに長さ \(N\) の配列を初期化すると、余計に \(O(N)\) かかってしまいます。

例えば、質問回数を \(K\) とすると、単純に毎回初期化すると全体で

\(O(K(N + Q))\)

かかります。
一方、この問題では \(KQ \leq 2 \times 10^7\) という制約があり、命令列のシミュレーション部分 \(O(KQ)\) は間に合うように作られています。
したがって、宝の回収状態の初期化を高速に行うことが重要です。

そこで、「タイムスタンプ」を使います。

各部屋 \(i\) について、最後にどの質問で宝を回収したかを seen[i] に記録します。
現在の質問番号を stamp とすると、

• seen[i] == stamp なら、この質問中ですでに部屋 \(i\) の宝を回収済み
• seen[i] != stamp なら、この質問中ではまだ未回収

と判断できます。

これにより、質問ごとに配列全体を初期化する必要がなくなります。

アルゴリズム

命令列 \(S\) を変更できるように、文字列ではなく bytearray として管理します。

各操作について、以下のように処理します。

操作 1 p c

命令列 \(S\) の \(p\) 文字目を \(c\) に変更します。

これは配列の 1 要素を書き換えるだけなので \(O(1)\) です。

操作 2

現在の命令列を最初から最後までシミュレーションします。

変数として以下を用意します。

• pos: 現在いる部屋、\(0\)-indexed で管理
• score: 現在のスコア
• stamp: 現在の質問番号
• seen[i]: 部屋 \(i\) の宝を最後に回収した質問番号

シミュレーションでは、命令を 1 文字ずつ見ます。

• L:
  • pos > 0 なら pos -= 1
• R:
  • pos < N - 1 なら pos += 1
• P:
  • seen[pos] != stamp なら、まだこの質問では未回収
  • seen[pos] = stamp として、score += A[pos]
• B:
  • pos = 0

最後に score を出力します。

たとえば、同じ部屋で P を複数回実行しても、seen[pos] == stamp になっているため、スコアに加算されるのは最初の 1 回だけです。

計算量

操作 2 の回数を \(K\) とします。

• 時間計算量: \(O(M + KQ)\)
  • 更新操作は 1 回あたり \(O(1)\)
  • 質問操作は 1 回あたり \(O(Q)\)
  • 制約より \(KQ \leq 2 \times 10^7\) なので十分高速です
• 空間計算量: \(O(N + Q)\)
  • 宝の回収状態管理に \(O(N)\)
  • 命令列の保持に \(O(Q)\)

実装のポイント

• 部屋番号は入力では \(1\)-indexed ですが、実装では \(0\)-indexed にすると扱いやすいです。

• 質問ごとに seen = [0] * N のように初期化すると遅くなる可能性があります。代わりに stamp を増やして管理します。

• 命令列は更新があるため、Python の通常の文字列ではなく bytearray を使うと、1 文字の書き換えを効率よく行えます。

• スコアは最大で \(N \times 10^9\) になり得るため、64 bit 整数が必要です。Python では整数の桁あふれを気にする必要はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, Q, M = map(int, input().split())
    A = list(map(int, input().split()))
    S = bytearray(input().strip())

    seen = [0] * N
    stamp = 0
    n_last = N - 1

    L = ord('L')
    R = ord('R')
    P = ord('P')
    B = ord('B')

    ans = []

    for _ in range(M):
        line = input().split()
        if line[0] == b'1':
            p = int(line[1]) - 1
            S[p] = line[2][0]
        else:
            stamp += 1
            pos = 0
            score = 0

            for c in S:
                if c == P:
                    if seen[pos] != stamp:
                        seen[pos] = stamp
                        score += A[pos]
                elif c == R:
                    if pos < n_last:
                        pos += 1
                elif c == L:
                    if pos:
                        pos -= 1
                else:
                    pos = 0

            ans.append(str(score))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。