kmjp's blog

競技プログラミング参加記です

AtCoder ARC #071 : E - TrBBnsformBBtion

FよりEの方が苦戦した。
http://arc071.contest.atcoder.jp/tasks/arc071_c

問題

A,Bで構成された文字列に対し、以下の変換を任意の順で任意回数行えるとする。

  • 文字列中の'A'1つを'BB'にする
  • 文字列中の'B'1つを'AA'にする
  • 文字列中の'AAA'1つを消す
  • 文字列中の'BBB'1つを消す

2つの文字列S,Tに対し、以下のクエリQ個に答えよ。

  • クエリとして4値(a,b,c,d)が与えられる。部分文字列S[a...b]をT[c...d]に変換可能か?

解法

変換前後で不変な評価値に注目し、最初と最後の文字列でその評価値が一致するかどうかを判定する、というアプローチが利用できる。
変換のルール、特に後ろの2つより、以下の評価値を用いることが考えられる。

  • 文字列中のAを1、Bを2とカウントし、その総和のmod 3を取る

あとは文字列S,Tに対し上記評価値の累積和を取っておけば、各クエリO(1)で回答できる。

一応、上記値が等しい空でない文字列P,Qに対し、P→Qが変換可能であることを示す。
Pを変換し、prefixをQと合わせていくことを考える。

  • P[i]=Q[i]ならP[i]は何もしない。ただし、P[i]がPの末尾で、Qがそれ以上に長い場合、A→BB→AAB等、P[i]の内容を変えず後ろに別の文字を生成する。
  • P[i]!=Q[i]なら、P[i]に前者2つのいずれかの変換を行い、P[i]=Q[i]とする。

上記手順で、Pの先頭|Q|文字がQと一致するようにできる。
Pの末尾に余計な文字が残るかも知れないが、それらはAかBにすべてそろえると、それらの文字列長が3の倍数になるので後者の変換によりすべて消せる。
(Pの先頭|Q|文字とQにおける評価値が一致するなら、Pの末尾の余計な分の評価値は0であり、AかBに文字をそろえると3の倍数になるはずである)

string S,T;
int SS[101010],TS[101010];
int Q;
int A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T>>Q;
	FOR(i,S.size()) SS[i+1]=SS[i]+(S[i]-'A')+1;
	FOR(i,T.size()) TS[i+1]=TS[i]+(T[i]-'A')+1;
	
	while(Q--) {
		cin>>A>>B>>C>>D;
		
		if((SS[B]-SS[A-1])%3==(TS[D]-TS[C-1])%3) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

まとめ

こういうの本番でとっさに解けなさそう。