JOI 春合宿2015 コピー＆ペースト2

問題文

http://joisc2015.contest.atcoder.jp/tasks/joisc2015_a

問題概要

文字列 S が与えられる．
S に対して，クエリが N 個投げられる．
各クエリは A, B, C を持ち，これは S の部分文字列 [A, B) を位置 C の直前にコピー挿入することを意味する．
最終的にできた S の先頭 K 文字を答えよ．
ただし，操作の途中で M 文字を超えた場合は，M 文字以降を削るものとする．

・制約
1 <= K <= 200
1 <= M <= 10^9
K <= S <= min(M, 2 * 10^5)
1 <= N <= 2 * 10^5

解法

K が小さいことに気が付かず，平衡二分探索木を書き始めて辛い思いをしていた．
実際，K が大きければこれで良い．
今回は 1 <= K <= 200 なので，O(KN) が間に合う．
やり方は，操作を逆順に見るという定番のテクで求めていく．

今 t 番目の文字が，ある操作の直前にどこにあったかを考えれば，最終的にどの文字になるかがわかる．
これをすべての 0 <= t < K に対してやる．
1. i 番目の操作で t 番目の文字が変化しない
2. i 番目の操作で t 番目の文字は挿入された文字の一部(overlap)になる．
3. i 番目の操作で t 番目の文字は挿入によって単に後ろにずれる．
のいずれかだから，場合分けしてやればよい．

ソースコード

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

int main() {
    int K, M, N;
    string S;
    cin >> K >> M >> S >> N;
    vector<int> A(N), B(N), C(N);
    for(int i = N - 1; i >= 0; --i) {
        cin >> A[i] >> B[i] >> C[i];
    }
    string res;
    for(int i = 0; i < K; ++i) {
        int t = i;
        for(int j = 0; j < N; ++j) {
            if(t < C[j]) {
                continue;
            } else if(t < C[j] + (B[j] - A[j])) {
                t = A[j] + t - C[j];
            } else {
                t = t - (B[j] - A[j]);
            }
        }
        res += S[t];
    }
    cout << res << endl;
}

感想

制約はちゃんと読もうね．