【ABC258】「C - Rotation」のメモ
概要
AtCoder Beginner Contest 258のC問題が解けなかったので、解説を見て得られた知見などを書いてみます。
コンテスト中に書いたコード
コンテスト中はコードを書けませんでした。愚直にやるコードを書くことはその気になればできましたが、TLEに決まっていると思って考察に全時間を費やしました。まあ、ダメだったわけですが…
「S の末尾の文字を削除し、先頭に挿入する」という操作をそのまま行うと文字列の長さに対して線形の計算量になるはずで、それをx回連続なので、間に合うわけがないと考えました。
文字列操作が定数時間になってくれれば、とか考えていました。
解説を受けて
公式解説はよくわからなかったので、こちらを参考にさせていただきました。
要するに文字列操作を実際にやったら時間がかかるので、やらずに済む方法を考えるべきだったということになります。
文字列は環状につながっているということでしっくりきました。先頭の文字は環状の文字列の中のどこを参照しているかということに相当し、「末尾の文字を削除し、先頭に挿入する」とは参照している文字列が左に一つずれるだけということになります。
そのため実際に文字列操作はせずとも、どこを参照しているのかという情報（インデックス）を更新していくだけでOKとなります。インデックスが文字列の範囲を超えたら、反対側に飛んだものとして計算しなおせばいいです。
この考え方で実装したのが以下です。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
int start = 0;
for(int i = 0; i < q; i++) {
int type, x;
cin >> type >> x;
if(type == 1) {
start -= x;
if(start < 0) {
start += n;
}
} else {
int i = start + x - 1;
if(i >= n) {
i -= n;
}
cout << s.at(i) << endl;
}
}
}
start がどこを参照しているかの情報です。初期値は先頭なので0です。 1 x のときはx分左にずらす、つまりマイナスすればいいです。負の数になったら右側に飛んだと考えればいいので、nを足します。xはn以下という制約があるため、nを足した後でも負の数ということはありません。（今回の実装ではstartは毎回文字列の範囲内に補正するため、xを引く前から既に負の数だったということもありません）
2 xのときはstartを起点として表示する文字の位置を決めます。xは1オリジンですが実装上は0オリジンなので-1する必要があります。
こちらは逆方向に文字列の範囲をはみ出す可能性があり、その場合は左側に飛んだと考えればいいのでnを引きます。上と同じ理由で、nを引いてもまだ範囲外ということはありません。
教訓
競プロ典型 90 問にこれとそっくりな問題があるとTwitterで教えてもらいました。なので、これはもう一つの典型パターンとして覚えてしまうのがよさそうです。
（こちらはズバリ「シフトする」と書いてあるので、こちらのほうがわかりやすいですが）
- 文字列操作を定数時間でできないか？ではなく、そもそもやらずに済む方法を考える
- 配列や文字列をシフトする問題は、実際に操作をやらずに位置だけ計算すれば解ける（範囲外になったら反対側に飛ぶ）
余談
反対側とつながっているというのは、実は同じ回のB問題でやっているんですよね…
意図的なヒントだったのでしょうか。
Discussion