概要

\(N\) 個の部屋に置かれた宝を、長さ \(Q\) の命令列 \(S\) に従ってロボットを操作して回収するシミュレーション問題です。命令列の一部を書き換えるクエリと、その時点での命令列を実行した際の合計スコアを求めるクエリの計 \(M\) 個の操作を処理します。

考察

この問題の最大のポイントは、制約に含まれる 「操作 2 の回数を \(K\) とすると、\(KQ \leq 2 \times 10^7\) である」 という条件です。

通常、命令列の長さ \(Q\) と操作回数 \(M\) が共に \(10^5\) 程度である場合、クエリごとに \(O(Q)\) のシミュレーションを行うと、最悪計算量は \(O(MQ) \approx 10^{10}\) となり、実行時間制限に間に合いません。しかし、本問題では「クエリごとのシミュレーション回数の合計」が十分に小さく抑えられているため、操作 2 が呼ばれるたびに愚直にシミュレーションを行う手法が有効です。

シミュレーションにおいては、以下の点に注意する必要があります。 - 宝の重複回収の判定: 同じ部屋の宝を 2 回以上回収してもスコアは加算されません。 - スコアの最大値: 宝の価値 \(A_i\) は最大 \(10^9\) であり、合計スコアは \(2^{31}-1\) を超える可能性があるため、64bit整数型（C++では long long）を使用する必要があります。 - 効率的な状態リセット: クエリごとに「どの部屋の宝を回収したか」という情報をリセットする必要があります。毎回 vector<bool> を \(O(N)\) かけて初期化すると、クエリごとの計算量が \(O(Q + N)\) となり、\(KQ\) の制約があっても \(KN\) が大きくなって TLE（実行時間制限超過）になる恐れがあります。

アルゴリズム

各操作 2 に対して、以下の手順でシミュレーションを行います。

1. 初期化:
   • ロボットの現在の部屋を 1 に設定します。
   • 現在の獲得スコアを 0 に設定します。
2. 命令の実行: 命令列 \(S\) を先頭から 1 文字ずつ確認し、以下の処理を行います。
   • L: 部屋番号が \(1\) より大きければ \(1\) 減らす。
   • R: 部屋番号が \(N\) より小さければ \(1\) 増やす。
   • P: 現在の部屋の宝が未回収なら、価値 \(A_i\) をスコアに加算し、「回収済み」とする。
   • B: 部屋番号を \(1\) に変更する。
3. 重複回収の管理（高速化）: 「回収済み」の判定には、配列 last_collected[room_id] を用意し、そこに「最後にその部屋の宝を回収したクエリ番号」を記録します。
   • if (last_collected[current_room] != query_count) であれば未回収と判定。
   • 回収時に last_collected[current_room] = query_count と更新。 これにより、配列の全要素を \(0\) で埋める初期化をクエリごとに行う必要がなくなります。

計算量

• 時間計算量: \(O(M + KQ)\)
  • 更新操作（操作 1）は \(O(1)\) です。
  • 質問操作（操作 2）は 1 回につき \(O(Q)\) かかります。
  • 制約より \(KQ \leq 2 \times 10^7\) であるため、制限時間内に十分収まります。
• 空間計算量: \(O(N + Q)\)
  • 宝の価値 \(A\)、回収判定用配列 last_collected で \(O(N)\)、命令列 \(S\) で \(O(Q)\) のメモリを使用します。

実装のポイント

• 入出力の高速化: \(M\) や \(Q\) が大きいため、C++では cin.tie(NULL); ios_base::sync_with_stdio(false); を使用して標準入出力を高速化することが推奨されます。

• 1-indexed と 0-indexed: 問題文の部屋番号や文字の位置は \(1\) から始まりますが、プログラム内の配列や文字列は通常 \(0\) から始まるため、添字の扱いに注意してください。

  ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/**
 * Problem: Robot Treasure Collection
 * This problem asks us to simulate a robot's movement and treasure collection
 * along a line of rooms based on a sequence of commands. There are updates
 * to the command sequence and queries to calculate the total score.
 * 
 * Given the constraint KQ <= 2 * 10^7 (where K is the number of queries and
 * Q is the command sequence length), a direct simulation for each query
 * is efficient enough.
 */

int main() {
    // Optimize standard I/O performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q, M;
    // Read the number of rooms N, length of command sequence Q, and number of operations M
    if (!(cin >> N >> Q >> M)) return 0;

    // Read the treasure values for each room (1 to N)
    // Using long long for treasure values as they can be up to 10^9
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    // Read the initial command sequence S
    string S;
    cin >> S;

    // last_collected[i] stores the ID of the last query in which the treasure 
    // in room i was collected. This allows us to track collected treasures 
    // for each query independently without clearing a boolean array in O(N).
    vector<int> last_collected(N + 1, 0);
    int query_count = 0;

    // Process each of the M operations
    for (int i = 0; i < M; ++i) {
        int op_type;
        cin >> op_type;
        if (op_type == 1) {
            // Update operation: change p-th command to character c
            int p;
            char c;
            cin >> p >> c;
            // p is 1-indexed in the problem, convert to 0-indexed for the string
            S[p - 1] = c;
        } else if (op_type == 2) {
            // Query operation: simulate the robot's execution of the command sequence S
            query_count++;
            long long current_score = 0;
            int current_room = 1;

            // Iterate through the command sequence and update the robot's state
            for (char cmd : S) {
                if (cmd == 'L') {
                    // Move left if possible
                    if (current_room > 1) current_room--;
                } else if (cmd == 'R') {
                    // Move right if possible
                    if (current_room < N) current_room++;
                } else if (cmd == 'P') {
                    // Collect treasure if it hasn't been collected in this specific query
                    if (last_collected[current_room] != query_count) {
                        current_score += A[current_room];
                        last_collected[current_room] = query_count;
                    }
                } else if (cmd == 'B') {
                    // Move directly back to room 1
                    current_room = 1;
                }
            }
            // Output the final score for the current simulation
            cout << current_score << "\n";
        }
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。