Atcoder ARC E: TrBBnsformBBtion

部分文字列の文字の順序は関係ない

つまり、部分文字列は任意の順序に並び替えることができる。

隣接する異なる2文字を入れ替えられることを示す。

AB

→BBB

→BBAA

→BBBBA

→BA

したがって、任意の隣接する2文字は入れ替えられる。なのでバブルソートの要領で任意の順位並び替えることができる。したがって、部分文字列の順序は関係ない。そのため、以下はA,Bの個数だけ考える。

A,Bの個数はmod 3で考えればいい。

"AAA"→""

"BBB"→""

のような操作が可能であった。実は空でない文字列について逆の操作が可能。

空でない文字列に対して""→"AAA"の操作が常にできることを示す。

(1)Aが少なくとも1個ある場合

1個のAに着目して

A

→BB

→AAB

→AAAA

よって

A""→A"AAA"

(2)Aが1個もない場合

文字列は空でないと仮定したので少なくとも1個のBがある。

1個のBに着目して

B

→AA

→BBA

→BAAA

よって

B""→B"AAA"

以上からAとBの個数はともに3個単位で任意の増減ができる。したがって、mod 3でA,Bの個数を数えれば良い。

これで全点対最短経路問題になる

事前にA,Bの部分和を計算しておく。

(Aの個数mod 3, Bの個数mod 3)

のような頂点を持ち、状態遷移を有向辺としたグラフを考える。

各クエリは、ある頂点uからvへ到達できるかということになる。

頂点数はたかだか9個なのでワーシャルフロイド法を使えばおしまい。