問題概要
A, Bのみからなる文字列$S$, $T$が与えられる.
$S$の部分文字列$s$について, 以下の4つの操作を好きなだけ行ってよいとき, $T$の部分文字列$t$に変換することは出来るかという判定クエリに$q$個答えなさい.
AをBBにする.BをAAにする.AAAを消す.BBBを消す.
制約
- $1 \leq |S|, |T|, q \leq 10^5$
- $s, t$はそれぞれ$S, T$の部分文字列.
考察
制約ををざっと見てみると, クエリの数が最大$10^5$個と多すぎる.
判定に使えるオーダーは高々$O(log|S|)$程度だけど, $\log$のオーダーで文字列処理するアルゴリズムなんてあるのか…?
$O(1)$臭が凄いから, 諸々証明出来るか試してみる.
仮説1. 操作は可逆である
真だったら, それぞれの文字の個数を$\mathrm{mod}\ 3$で考えることにより, 操作3,4とその逆は考慮に入れる必要が無くなる.
操作1, 2について,
BB→AAAA→A操作3, 4については, 操作後に1文字は必ず残っているため, その1文字が
Aの場合とBの場合に分けて考える.A→BB→AAAAB→AA→ABB→AAABB→AA→BBA→BAAA
よって, 全ての操作が可逆であると分かった.
仮説2. $s, t$の並びは結果に影響しない
真だったら, それぞれの文字の個数について考えるだけで良くなる. (偽だったら, $s, t$について走査しなきゃいけないから$O(1)$じゃない.)
以下便宜上, 文字Aが$n$個並んだ文字列を[A, n]と表記する.
自然数$a, b$について, [A, a] + [B, b]になんらかの操作をすることにより[B, 1] + [A, a] + [B, b - 1]に変換できたなら, 各操作におけるA, Bの対称性より, その操作を繰り返すと任意の並びにできる(はず).
実際に, 以下のように操作が行える.
[A, a] + [B, b][A, a] + [B, 1] + [B, b - 1][A, a] + [A, 2] + [B, b - 1][A, 1] + [A, 1] + [A, a] + [B, b - 1][B, 2] + [B, 2] + [A, a] + [B, b - 1][B, 3] + [B, 1] + [A, a] + [B, b - 1][B, 1] + [A, a] + [B, b - 1]
仮説1より, この逆の操作も行えるため, 示された(と思う).
最後の詰め
先ほど述べたように, 操作3, 4とその逆は考える必要がなくなった(操作1,2を行って, 最後に差分が3の倍数であれば変換可能と分かるため).
$s$の中のA, Bの個数をそれぞれ$a, b$個, $t$の中のそれらの個数をそれぞれ$a + m, b + n$個とする.
今, 操作1を$p$回, 操作2を$q$回行うと, Aは$q - p$個, Bは$p - q$個増えるため, $a + q - p, b + p - q$個となる.
よって, $a + m \equiv a + q - p,\ b + n \equiv b + p - q\ (\mathrm{mod}\ 3)$を満たしていれば良い.
ちょっと式変形して$-m\equiv n(\mathrm{mod}\ 3)$ならばYES, そうでないならばNOとなる.
実装
imos法で任意区間におけるAの個数を$O(1)$で取り出せるようにしておいて, あとは上の判定式に突っ込んで出力するだけ.
提出コード(C++🔆)
string S, T;
int Q;
ll umod(ll a) {
ll ret = a % 3;
if (ret < 0) return ret + 3;
return ret;
}
signed main() {
cin >> S >> T;
int len_s = S.size();
int len_t = T.size();
CumulativeSum<int> S_A(len_s), T_A(len_t);
REP(i, len_s) if (S[i] == 'A') S_A.add(i, 1);
REP(i, len_t) if (T[i] == 'A') T_A.add(i, 1);
S_A.build();
T_A.build();
int a, b, c, d;
cin >> Q;
while (Q--) {
cin >> a >> b >> c >> d;
--a, --b, --c, --d;
int s_a = (int)S_A.query(a, b), s_b = (b - a + 1) - s_a;
int t_a = (int)T_A.query(c, d), t_b = (d - c + 1) - t_a;
int dif_a = t_a - s_a;
int dif_b = t_b - s_b;
cout << ((umod(dif_a) == umod(dif_b)) ? "YES" : "NO") << endl;
}
}