【AtCoder】ARC145 A - "AB Palindrome"

一見複雑そうに見えるが，ある規則を見つけると，考えるべき問題は単純になる．

問題概要
- 制約
考察
解法
- 実装 (C++)
感想

問題概要

atcoder.jp

英文字の'A', 'B'からなる長さ $N$ 文字列 $S$ が与えられる．
$S$ 中の隣接する2文字を"AB"に置き換える操作を，0回以上の任意の回数繰り返すことで，回文を得られるか判定せよ．

制約

$2 \leq N \leq 2 \times 10^5$

考察

まず，利用できそうな置き換え方法を探ってみる．

任意の位置から順方向に（ $S[i:i+2], S[i+1:i+3], \cdots$ の順で）"AB"に置き換えると，"AAA...AAB"という部分文字列が作れる．
同様に，任意の位置から逆方向に（ $S[i-2:i], S[i-3:i-1], \cdots$ の順で）"AB"に置きかえると，"ABB...BBB"という部分文字列が作れる．

これらより

$S[0]=\rm{'B'}$ の場合は，"BAA...AAB"
$S[N-1]=\rm{'A'}$ の場合は，"ABB...BBA"

とすれば回文ができる．

あとは

先頭 $S[0]$ を'A'から'B'に
末尾 $S[N-1]$ を'B'から'A'に

置き換えることができないことなどに注意しながら， $S[0]=\rm{'A'}$ の場合と， $S[n-1]=\rm{'B'}$ の場合を考えればよい．

（ただし， $N=2$ の場合は上記が適用ができないので別に考える必要がある．）

解法

$N=2$ の場合．

$S=\rm{"AA"}$ または $S=\rm{"BB"}$ のとき：すでに回文である．
$S=\rm{"AB"}$ または $S=\rm{"BA"}$ のとき：置換しても"AB"しかできず，回文を得ることはできない．

$N \geq 3$ の場合．

$S[0], S[N-1]$ について，それぞれ場合分けして考える．

$S[0]=\rm{'A'}$ のとき
- $S[N-1]=\rm{'A'}$ の場合：回文"ABB...BBA"を得る．
- $S[N-1]=\rm{'B'}$ の場合：先頭 $S[0]$ と末尾 $S[N-1]$ はどちらも置き換えできないので，回文を得られない．
$S[0]=\rm{'B'}$ のとき：回文"BAA...AAB"を得る．

以上■

実装 (C++)

#include <iostream>
#include <string>
using namespace std;

int main(){
    int n;
    string s;
    cin>>n>>s;
    
    bool ans;
    if(n==2){
        if(s=="AA" or s=="BB") ans=true;
        else ans=false;
    }else{
        if(s[0]=='A'){
            if(s[n-1]=='A') ans=true;
            else ans=false;
        }else{
            ans=true;
        }
    }
    
    cout<<(ans?"Yes":"No")<<endl;
}

感想

本番はDPで考えて複雑になり，解けなかったです......．上手いこと利用できそうな操作方法を見つけ出すのがカギでしたね．

久々のARCだったんですが，やはり典型解法が多いABCとは違い，頭の柔軟さがより求められる印象です．
ARCの過去問もいっぱい解いて慣れようと思います．