第二回 アルゴリズム実技検定 G - ストリング・クエリ 解説
問題
問題文は本家サイトにあります：第二回 アルゴリズム実技検定 G - ストリング・クエリ
問題概要
文字列 $S$ （はじめは空文字）に対して、与えられた $Q$ 回の操作を行いなさい。なお、操作は2種類あり、 $i$ 回目の操作 $T_i$ の内容は以下の通り。
$T_i=1$ のとき：
英小文字 $C_i$ と整数 $X_i$ が与えられる。 $S$ の末尾に $C_i$ を $X_i$ 個追加する。
$T_i=2$ のとき：
整数 $D_i$ が与えられる。 $S$ の先頭から $D_i$ 文字を削除する。 'a', 'b', …, 'z' の各文字が削除された数をそれぞれ求め、それらを2乗し、すべてを足し合わせた結果を出力する。
制約
はじめの段階で $S$ は空文字
$C_i$ は英小文字
$1\leqq Q \leqq 10^5$
$1\leqq X_i \leqq 10^5$
$1\leqq D_i \leqq 10^5$
解説
'1 a 5' と '2 3' が入力されれば、'aaaaa' が 'aa' になるということなので、 $3^2=9$ を出力することになります。さらに '1 t 8' と '1 c 10' が入力された後に '2 21' が入力された場合を考えてみます。このとき、削除する直前の文字列 $S$ の中身は
aattttttttcccccccccc
になっています。この先頭から21文字を削除すると、a を2文字、 t を8文字、 c を10文字削除することになる（結果として、 $S$ は空文字になる）ので、\[ 2^2+8^2+10^2=168 \]を出力することになります。
やるべきことはこのような処理なのですが、問題にある通りに文字列を作るのは効率が悪いですね。長さが $10^{10}$ 程度になってしまう可能性もあります。そこで、各文字が何文字続いているかを管理することにしましょう。
先ほどの例であれば、文字列を作らずに「a が2文字、t が8文字、c が10文字続く」と管理しておけば十分だとわかります。「5文字消す」とか「13文字消す」といった処理は、前から順番に処理をしていけばいいです。こちらの方が管理しやすいです。
このように、データを蓄積した後、前から順番に処理を行う場合には、キュー queue を使うと楽になることが多いです。先ほどの例で13文字消す場合には、はじめの a を2文字消して残り11文字消す、続いて t を8文字消して残り3文字消す、というように処理をしていく、という流れです。
aが2、tが8、cが10 ↓ 13文字消したい ↓ はじめのaを全部消す tが8、cが10 ↓ あと 11文字消したい ↓ はじめのtを全部消す ：
ただ、消しきれずに文字が残ってしまう場合に困ってしまいます。c が10文字残っているところから3文字消した場合、c は残り7文字にして、以降の操作を続けていきたいですね。後ろに追加するだけなく、前に追加する処理も行いたいので、queue の代わりに、両端キュー deque を使うことにしましょう。
以上を踏まえると、C++では以下のように書くことができます。コードの下に、コードの説明が続きます。
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
int main() {
ll Q; cin >> Q;
deque<pair<char, ll>> q;
for (ll i = 0; i < Q; i++) {
ll T; cin >> T;
if (T == 1) {
char C; ll X;
cin >> C >> X;
q.emplace_back(make_pair(C, X));
} else {
ll D; cin >> D;
vector<ll> cnt(26, 0);
while (!q.empty()) {
pair<char, ll> p = q.front();
q.pop_front();
if (D >= p.second) {
cnt[p.first - 'a'] += p.second;
D -= p.second;
} else {
cnt[p.first - 'a'] += D;
p.second -= D;
q.emplace_front(p);
break;
}
}
ll ans = 0;
for (ll j = 0; j < 26; j++) {
ans += (cnt[j] * cnt[j]);
}
cout << ans << '\n';
}
}
return 0;
}T == 1 の場合は、文字列 C とその個数 X をペアにして、キューの後ろに追加するだけです。これで操作は終わりです。
T == 2 の場合は、D 文字削除する処理を行います。まず、キューの先頭に入っているペアを取り出します。もし、今残っている文字が全部消せるなら、全部消します。 D は今消した分だけ減らしておきます。そして、次のペアへと進みます。
もし、これから消したい文字数より、今残っている文字数の方が多い場合は、今残っている文字数を減らして、キューの先頭に戻し、削除処理を終了します。
こうして、キューが空になるか、D 文字分削除し終わるか、どちらかになれば、キューに対する処理はおしまいです。削除した文字数を各文字ごとに集計しておき、2乗の和を計算して出力します。これで操作は終わりです。
