Codeforces #1504A Déjà Vu

문제

https://codeforces.com/contest/1504/problem/A

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    string f = 'a' + s;
    string b = s + 'a';
    for(int i = 0; i < (n+1)/2; i++){
        if(f[i] != f[(n+1)-i-1]){
            cout << "YES\n";
            cout << f << "\n";
            return;
        }
    }
    for(int i = 0; i < (n+1)/2; i++){
        if(b[i] != b[(n+1)-i-1]){
            cout << "YES\n";
            cout << b << "\n";
            return;
        }
    }
    cout << "NO\n";
}

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

대회 때 모든 시간을 써서 고민을 해 봐도 풀지 못했던 문제. 튜토리얼에서는 'a' + s 와 s + 'a' 가 동시에 펠린드롬인 수는 모든 문자열이 'a' 일 때를 제외하곤 존재 할 수 없음을 증명하여 풀이한다. 구성적 알고리즘 싫어.