[AGC055] B - ABC Supremacy
[Q] https://atcoder.jp/contests/agc055/tasks/agc055_b
いろいろ考察してみた結果。
1. ABC, BCA, CAB がきたら、取り除いちゃっていい。
2. のこりカスの順番は変えられない。
Q. ABCAA ?
A. ABCを1塊として、残りのAAの位置がまとまって動く。
ABC A A
= A ABC A
= A A ABC
Q. AABCB ?
A.
A ABC B = (A BCA B)
= ABC A B = (A B CAB)
= A B ABC
残りかすの A B の順番が変わらないのがわかる。
Q. ABCを取り除いた結果、あらたにABCができる場合もある?(2TLE)
Q. AAAABCBCBCBC
A. これは ABC が 4個できる。
A. 先頭からお尻まで走査するときに、
今見てる文字と、その1つ前と、その2つ前を組み合わせたらABCになるかを確認すればよさそう。
Q. 例2
4
ABCA
BCAB
S="ABCA"
T="BCAB" として管理。
1. deque<char> Q に入れながら S を探索。
1) A
Q = {A}
2) B
Q= {A B}
3) C
Q.size() > 1なのでABCか確認。
Q = {A B} + C
これは ABC になるので Q.pop_back()を2回。
Q = {}
4) A
Q = {A}
S = "A"になった。
2. Tを探索。
1) B
Q = {B}
2) C
Q = {B C}
3) A
Q.size() > 1 なので、ABC確認。
Q = {B C} + A
これは BCA になるので Q から2個除く。
Q = {}
4) B
Q = {B}
T = "B" になった。
S != Tなので、
A. NO
実装
ll N;
string base[3]={"ABC", "BCA", "CAB"};
bool is_abc(string s){
rep(i, 3){
if (s==base[i]) return true;
}
return false;
}
string del_abc(string S){
deque<char> Q;
string ret;
rep(i, N){
ll qsz = Q.size();
bool ok = false;
if (qsz>1){
string test;
test += Q[qsz-2];
test += Q[qsz-1];
test += S[i];
if (is_abc(test)) ok = true;
}
if (ok){
Q.pop_back();
Q.pop_back();
}
else Q.push_back(S[i]);
}
while (!Q.empty()){
ret += Q[0];
Q.pop_front();
}
return ret;
}
int main(){
cincout();
string S, T;
cin >> N >> S >> T;
string s = del_abc(S);
string t = del_abc(T);
// cout << s << endl;
// cout << t << endl;
if (s==t) cout << "YES" << endl;
else cout << "NO" << endl;
}
この記事が気に入ったらサポートをしてみませんか?