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; } }
まとめ
こういうの本番でとっさに解けなさそう。