joi春合宿2015 day1-1:Copy and Paste 2

問題文

http://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d1.pdf

解法

最初はなにをしていいか全くわからなかった。

先頭K文字だけを記憶すればいけるのでは？？という壮絶な嘘解法を思いついたが、最後のCopy and Pasteの操作で後ろの方から文字列を持ってこられたら詰むなぁということに気付いて悲しくなった。しかし、このときの考察のおかげで解けた感じがある。

Copy and Pasteの操作を逆順に見ていけば、O(N)で1文字求められる。K文字求めたいのでO(KN)で解ける。

30行程度で実装が終わったので、絶対嘘解法だと思ったけどACしてびっくりした。かなり良問だと思ったなど。

コード

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

int K,M,N;
string S;

int L[200000],R[200000],C[200000];

int main(){
    cin>>K>>M>>S>>N;
    for(int i=0;i<N;i++)cin>>L[i]>>R[i]>>C[i];

    for(int k=0;k<K;k++){
        int pos=k;
        for(int i=N-1;i>=0;i--){
            if(pos<C[i])continue;
            if(C[i]+R[i]-L[i]<=pos)pos-=R[i]-L[i];
            else pos=L[i]+pos-C[i];
        }
        cout<<S[pos];
    }
    cout<<endl;
    return 0;
}