ARC 071 E - TrBBnsformBBtion

• 問題
• AC

まずは操作が可逆かどうか考えてみる。操作1は逆操作が可能である:

• BB → AAB → AAAA → A
• AA → BAA → BBBB → B

操作2は、文字列が空でない限り逆操作が可能である:

• A → BB → AAB → ABBB
• A → BB → BAA → BBBA
• B → AA → BBA → BAAA
• B → AA → ABB → AAAB

したがって、文字列の集合はいくつかの同値類に分割できそうと思える。そこで、それらをもっとも短い文字列で代表させることを考える。

• AB → AAA → 空
• BA → BBB → 空
• AA → B
• BB → A

に従うと、長さ2以上の文字列は必ず短くできる。つまり、任意の文字列は、できるだけ短い文字列に変換するとA, B, 空のいずれかになり、文字列の集合が3つの同値類に分割できるとわかる。¹

3つの同値類をそれぞれ$A, B, O$で表すことにして、文字をつなげる操作を$+$で表すと、演算の性質は以下のようになっている。

$A+B = B+A = O \\ A+A = B \\ B+B =A \\ A + O = O + A = A \\ B + O = O + B = B$

これは${\mathbb Z}/3{\mathbb Z}$と同型なので、$\mod 3$で文字列$S$と$T$の累積和を取っておけば、クエリには${\mathcal O}(1)$で答えられる。²

---

1. 文字列 $a$ → 空 → 文字列 $b$という変換は不可能なのが気になるが、空になる直前は必ずAAAかBBBのどちらかになっていて、AAA → BBBBBB → BBBとその逆の変換が可能なので問題ない。 ↩︎

2. 上では、そもそも文字列A, Bと空の文字列は本当に相互変換できないのか確かめていなかった。しかし、考察をここまで進めると、文字Aを$1$、文字Bを$2$として$\mod 3$で和を見れば、2種類の変換の前後で総和が変化しないことがわかり、それが証明になっている。 ↩︎