https://yukicoder.me/problems/no/1021
解説
https://yukicoder.me/submissions/462597
さて、初めてこういう問題に取り組む人は、どういう所から考え始めればいいかわからないかもしれない。
こういう操作を行う問題の方針の1つである「差分だけ計算する」という方針で考えてみる。
タイプLを考えてみると、ほぼ左に移るが、最左の要素ははみ出すが、左から二番目の要素に足される。
はみ出した部分を二番目の要素に足すこと以外を見てみると、シフト操作になっている。
シフト操作は全部を移動させるのではなく、オフセットを移すというやり方がある。
つまりは、以下のような感じ。
なので、今の状況のL,Rを持っておき、タイプLであればL++,R++、タイプRであればL--,R--してやればシフトはできる。
はみ出した分だけ、別途足し合わせてやれば操作はO(1)で行えるので、M回やっても問題ない。
注意点として、L,Rは負の数になる可能性があるので、L=0,R=N-1スタートとせずに、
L=M,R=M+N-1のような配列の真ん中ぐらいに配置してスタートするといい。
int N, M, A[201010]; string S; int buf[601010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, N) cin >> A[i]; cin >> S; int L = M, R = M + N - 1; rep(i, 0, N) buf[M + i] = A[i]; fore(c, S) { if (c == 'L') { L++; R++; buf[L] += buf[L - 1]; buf[L - 1] = 0; } else { L--; R--; buf[R] += buf[R + 1]; buf[R + 1] = 0; } } rep(i, L, R + 1) { if(i != L) printf(" "); printf("%d", buf[i]); } printf("\n"); }