AtCoder Regular Contest #071 E問題 - TrBBnsformBBtion

Source

AtCoder Regular Contest #071
問題文

問題概要

文字列に対する以下の $4$ 種類の操作を考える.

  1. 文字列中の任意の1箇所の $\verb|A|$ を $\verb|BB|$ に置き換える
  2. 文字列中の任意の1箇所の $\verb|B|$ を $\verb|AA|$ に置き換える
  3. 文字列中の任意の1箇所の $\verb|AAA|$ を削除する
  4. 文字列中の任意の1箇所の $\verb|BBB|$ を削除する

アルファベット $\verb|A|$,$\verb|B|$ のみからなる文字列 $S,T$ が与えられる.
また,クエリが $Q$ 個与えられ,$i$ 番目のクエリは $4$ つの整数 $A_i, B_i, C_i, D_i$ からなるので,
$S[A_i,B_i]$ を上の4種類の操作を好きな順番で好きなだけ行って良いので文字列 $T[C_i,D_i]$ に変換できるかどうかを判定しなければいけない.
ここで,$s[i,j]$ は文字列 $s$ の $i$ 文字目から $j$ 文字目までで構成される部分文字列を意味する.

解法

文字列 $X$ に対して,関数 $f(X)$ の値を
 $\verb|A|$ の数 + $\verb|B|$ の数 × 2 mod 3
とする.
文字列 $X$ に対して,4種類のいずれの操作によっても $f(X)$ の値が不変であり,逆に $f(X)$ の値が同じなら,互いに4種類の操作で互いに変換可能であることがわかる.
よって,$\verb|A|$ を $1$,$\verb|B|$ を $2$ と起き直して,対応する区間の和のmod 3が等しいかどうかを調べれば良い.
それは,最初に累積和を求めておくと,各クエリに対して $O(1)$ 時間で答えることができる.
合計では,時間計算量 $O(|S|+|T|+Q)$ 程度.

cLayversion 20170408-3)のコード

C++に変換後のコードはこちら

char S[100010], T[100010];
int lenS, lenT;
int Q, A, B, C, D;

int sum1[100010], sum2[100010];
{
  rd(S,T,Q);
  lenS = strlen(S);
  lenT = strlen(T);

  S[0..lenS-1] = (S[0..lenS-1]=='A')?2:1;
  T[0..lenT-1] = (T[0..lenT-1]=='A')?2:1;
  sum1[1..lenS] = sum1[0..] + S[0..];
  sum2[1..lenT] = sum2[0..] + T[0..];
  
  while(Q--){
    rd(A,B,C,D);
    if( (sum1[B]-sum1[A-1])%3 == (sum2[D]-sum2[C-1])%3 ) wt("YES"); else wt("NO");
  }
}

Current time: 2017年07月22日09時42分33秒
Last modified: 2017年04月08日22時50分12秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC071 ARC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: