概要

一列に並んだ \(N\) 個の部屋をロボットが命令列に従って移動・宝回収するシミュレーション問題。命令列の一部書き換えと、現在の命令列での獲得スコアの問い合わせに答える。

考察

まず、操作 2（スコアの問い合わせ）のたびにロボットは完全に初期状態からシミュレーションをやり直す点に注目します。つまり、各問い合わせは独立です。

素朴に毎回長さ \(Q\) の命令列を先頭から1文字ずつシミュレーションすると、1回あたり \(O(Q)\) かかります。問い合わせが \(K\) 回あれば全体で \(O(KQ)\) です。

一見すると \(Q \leq 10^5\)、\(M \leq 10^5\) なので \(KQ\) が最大 \(10^{10}\) になりそうで心配ですが、制約に \(KQ \leq 2 \times 10^7\) という条件が明記されています。これは「問い合わせ回数が多いときは命令列が短く、命令列が長いときは問い合わせ回数が少ない」ことを保証しており、愚直シミュレーションで十分間に合うことを意味します。

アルゴリズム

各操作を順に処理します。

• 操作 1 p c: 命令列 \(S\) の \(p\) 文字目（0-indexed で \(p-1\)）を文字 \(c\) に書き換えるだけ。\(O(1)\)。
• 操作 2: ロボットを部屋 \(1\)、スコア \(0\)、全宝未回収の初期状態から、命令列 \(S\) を先頭から1文字ずつシミュレーション。
  • L: 部屋番号が \(1\) より大きければ左へ移動
  • R: 部屋番号が \(N\) より小さければ右へ移動
  • P: 現在の部屋の宝が未回収なら回収してスコア加算
  • B: 部屋 \(1\) に戻る

宝の回収済み判定には bool collected[] 配列を使います。シミュレーション終了後、回収した部屋だけを記録しておき、それらのフラグをリセットすることで、毎回配列全体を初期化する \(O(N)\) のコストを回避しています。

具体例

部屋が \([10, 20, 30]\)（\(N=3\)）、命令列が RRPP の場合： 1. R: 部屋 \(1 \to 2\) 2. R: 部屋 \(2 \to 3\) 3. P: 部屋 \(3\) の宝（価値 \(30\)）を回収。スコア \(= 30\) 4. P: 部屋 \(3\) は回収済み。何もしない

最終スコアは \(30\)。

計算量

• 時間計算量: \(O(M + KQ)\)（\(K\) は操作 2 の回数）。制約より \(KQ \leq 2 \times 10^7\) なので十分高速。
• 空間計算量: \(O(N + Q)\)（宝の価値配列と命令列の保持）

実装のポイント

• 回収済みフラグのリセット: シミュレーションごとに collected 配列全体を \(O(N)\) で初期化するのではなく、実際に回収した部屋番号を visited に記録し、シミュレーション後にそれらだけリセットする。これにより各シミュレーションのコストが \(O(Q)\) に収まる。

• static bool collected[200001]: グローバルまたは static 配列として確保することで、初期値が \(0\)（false）であることが保証され、毎回の明示的な初期化が不要になる。

• C++ での高速 I/O: ios_base::sync_with_stdio(false) と cin.tie(NULL) により入出力を高速化し、制限時間内に収める。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q, M;
    cin >> N >> Q >> M;
    
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    
    string S;
    cin >> S;
    
    static bool collected[200001];
    
    for (int i = 0; i < M; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int p;
            char c;
            cin >> p >> c;
            S[p - 1] = c;
        } else {
            long long score = 0;
            int pos = 1;
            vector<int> visited;
            for (int j = 0; j < Q; j++) {
                char cmd = S[j];
                if (cmd == 'L') {
                    if (pos > 1) pos--;
                } else if (cmd == 'R') {
                    if (pos < N) pos++;
                } else if (cmd == 'P') {
                    if (!collected[pos]) {
                        collected[pos] = true;
                        score += A[pos];
                        visited.push_back(pos);
                    }
                } else { // B
                    pos = 1;
                }
            }
            for (int v : visited) collected[v] = false;
            cout << score << '\n';
        }
    }
    
    return 0;
}

この解説は claude4.6opus-thinking によって生成されました。