@morio_progの精進日記

解いた競プロの問題をつらつらと。(AtCoder: morio__)

【ARC071】E - TrBBnsformBBtion

問題概要

'A', 'B'のみからなる文字列S, Tが与えられる. Sの部分文字列sについて, 以下の4つの操作を好きなだけ行ってよいとき, Tの部分文字列tに変換することは出来るかという判定クエリにq個答えなさい.

  1. 'A'を'BB'にする.
  2. 'B'を'AA'にする.
  3. 'AAA'を消す.
  4. 'BBB'を消す.

制約

  • 1 <= |S|, |T|, q <= 105
  • s, tはそれぞれS, Tの部分文字列.

考察

制約ををざっと見てみると, クエリの数が最大105個と多すぎる. 判定に使えるオーダーは高々O(log|S|)程度だけど, logのオーダーで文字列処理するアルゴリズムなんてあるのか...? O(1)臭が凄いから, 諸々証明出来るか試してみる.

仮説1. 操作は可逆である.

真だったら, それぞれの文字の個数をmod 3で考えることにより, 操作3,4とその逆は考慮に入れる必要が無くなる.

操作1,2について, BB → AAAA → A 操作3,4については, 操作後に1文字は必ず残っているため, その1文字がAの場合とBの場合に分けて考える.

  • A → BB → AAAA
  • B → AA → ABB → AAAB
  • B → 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"となる. ああ美しい😇

実装

いもす法で任意区間における'A'の個数をO(1)で取り出せるようにしておいて, あとは上の判定式に突っ込んで出力するだけ🙌

ACコード(C++🔆)

// 未整形より工事中