Deletions of Two Adjacent Letters-Codeforces

投稿日：2022/04/13 更新日:2022/04/13

問題

長さが奇数の文字列 $s$ が与えられます。長さが $1$ になるまで以下の操作を繰り返します。

任意の隣接する2文字を $s$ から選び削除する。つまり、 $s = s_1s_2...s_n$ に対し任意の $i(1 \leqq i < n)$ に対し操作を行うと $s = s_1s_2...s_{i-1}s_{i+2}...s_n$ となる。

文字列 $s$ と文字 $c$ が与えらるので操作終了後 $s = c$ とできるか判定してください。

解法

$s$ の $i$ 番目の文字を残すとします。 $s_1...s_{i-1}s_is_{i+1}...s_n$ と文字列を示した時、 $s_i$ の前後にある $s_1...s_{i-1}$ と $s_{i+1}...s_n$ を削除する必要があります。2個づつ削除できるためどちらも偶数でなければなりません。
したがって、残す文字列の前後が偶数個か判定すれば良いです。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    string s;
    char c;
    cin >> s >> c;

    int n = s.length();
    int count_l = 0, count_r = n-1;
    for(int i = 0;i < n; ++i){
        if(s[i] == c){
            if(count_l%2 == 0 && count_r%2 == 0){
                cout << "YES" << endl;
                return;
            }  
        }
        count_l++;
        count_r--;
    }
    cout << "NO" << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}