AtCoder Regular Contest #071
問題文
文字列に対する以下の $4$ 種類の操作を考える.
アルファベット $\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)$ 程度.
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: 2024年03月29日09時24分45秒
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)