ARC071E TrBBnsformBBtion
問題概要
'A', 'B'からなる文字列SとTがある。（長さは10^5以下）
以下の置換操作を任意に行える。
- "A" → "BB"
- "B" → "AA"
- "AAA" → ""
- "BBB" → ""
クエリa, b, c, dがq回与えられる。（q<=10^5）
それぞれのクエリについて、Sのa文字目からb文字目までの文字列を、Tのc文字目からd文字目までの文字列に変換できるか求めよ。
考察
無理では？？？？
と思いつつも文字列の遷移を書いていると、文字列に対する変換には逆変換が存在することが分かる。
"A" → "BB"なら"BB" → "AAAA" → "A"といった具合。
このことから、S, Tそれぞれを目標となる文字列sに変換できればYESなことが分かる。
また、"AAA" → ""に対して"" → "AAA"は通常不可能だが、置換処理の際に運用でカバーしてもらうので問題ない。
ここで、sは'A'のみで構成された最短の文字列とする。
'B'を全て"B" → "AA"で変換し、"AAA" → ""を可能な限り使うとsは"", "A", "AA"のいずれかになる。
これは区間の'A', 'B'それぞれの数から分かるので、累積和で簡単に求まる。
ので、S, Tそれぞれの区間から目標文字列の長さを調べ、一致するか判断する。
提出
→AC
やったぜ。
