Codeforces Round #706 (Div. 2) A

A. Split it!

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        if(k == 0){
            cout << "YES\n";
            continue;
        }
        if(n < 2*k+1){
            cout << "NO\n";
            continue;
        }
        bool valid = false;
        for(int j = 0; j < 100; j++){
            string a, Ra;
            if((n-1)/2-j < k) continue;
            for(int i = 0; i < (n-1)/2-j; i++)
                a += s[i];
            for(int i = n/2+1+j; i < n; i++)
                Ra += s[i];
            reverse(all(Ra));
            if(a == Ra) valid = true;
        }
        if(valid) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

문자열 s 를 k 값에 따라 a1 + a2 + ... + ak + ak+1 + R(ak) + R(ak-1) + ... + R(a2) + R(a1) 으로 나눌 수 있다고 한다. 문자열 a 는 어떤 구성을 띄어도 상관이 없다. 단, a 와 reverse 처리된 R(a) 가 쌍으로 존재할 경우 두 값이 같아야 YES 를, 하나라도 같지 않으면 NO 를 출력한다.

문제에서는 a 가 빈 문자열일 수 없다고 했다. n 이 2*k+1 보다 작은 경우는 무조건 NO 를 출력하도록 한다.

k == 0 인 경우를 제외한 모든 케이스가 ak+1 값을 중심으로 양쪽에 문자의 개수가 n/2 개 존재한다. ak+1 의 문자를 좌우로 하나씩 늘리면 양쪽 문자 개수가 하나씩 줄어들게 되는데, 개수가 k 개 미만이 되기 전 까지의 경우를 모두 조사해 주면 ac 를 받을 수 있다.

후기

문제플 60% 정도만 이해하고 구현을 하는 바람에 A 번 문제를 푸는데 한시간 이상을 사용했다...

제출을 한번 할 때 마다 반례를 하나씩 찾아야 했는데, 총 3개의 반례를 찾고서야 문제를 완벽하게 이해하고 구현했다.

B 번 문제는 40분 동안 고민하고 구현을 하다 시간이 없어 제출하지 못했는데 끝나고 나서 보니 시간초과가 나는 풀이였고 수학 문제였다.

규칙을 찾아 수식을 세웠어야 했는데 mex 함수의 시간복잡도를 줄이는데에만 혈안이 되어 풀지 못했던 것 같다.