Codeforces Round #715 (Div. 2) A, B

A. Average Height

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;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> o, e;
        int t;
        for(int i = 0; i < n; i++){
            cin >> t;
            if(t%2 == 0) e.push_back(t);
            else o.push_back(t);
        }
        for(int i = 0; i < o.size(); i++) cout << o[i] << " ";
        for(int i = 0; i < e.size(); i++) cout << e[i] << " ";
        cout << "\n";
    }
    return 0;
}

인접한 두 원소 u, v 합을 2로 나눈 값이 정수이면 photogentic 하다고 할 때, photogentic 한 쌍이 최대한 연속적이게 나타나게끔 순서를 고치려고 한다. 인접한 두 원소의 합이 2로 나누어 떨어지려면 홀수 + 홀수 또는 짝수 + 짝수 조합이 되어야 하므로 홀수와 짝수를 분리하여 출력하면 된다.

B. TMT Document

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;

bool solve(){
    int n;
    cin >> n;
    string a;
    cin >> a;
    int tc = count(all(a), 'T');
    int mc = count(all(a), 'M');
    if(mc*2 != tc) return false;
    vector<int> tpS(n+1, 0);
    vector<int> mpS(n+1, 0);
    tpS[1] = a[0] == 'T' ? 1 : 0;
    mpS[1] = a[0] == 'M' ? 1 : 0;
    for(int i = 2; i < n+1; i++){
        tpS[i] = a[i-1] == 'T' ? 1 : 0;
        tpS[i] += tpS[i-1];
        mpS[i] = a[i-1] == 'M' ? 1 : 0;
        mpS[i] += mpS[i-1];
    }
    for(int i = 1; i <= n; i++){
        if(a[i-1] == 'M'){
            int tl = tpS[i-1]-tpS[0];
            int tr = tpS[n]-tpS[i];
            int ml = mpS[i-1]-mpS[0];
            int mr = mpS[n]-mpS[i];
            if(tl-ml < 1 || tr-mr < 1) return false;
        }
    }
    return true;
}

int main(){
    fastio;
    int t;
    cin >> t;
    while(t--){
        if(solve()) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

3의 배수 길이의 문자열이 주어질 때 모든 문자가 인접함과 관계없이 TMT 이룰 수 있는지를 확인하는 문제이다. 첫번째로 주어진 문자열의 T 개수가 M 의 두배인지를 검사한다. 두번째로 문자열의 모든 M 에 대해서 좌, 우에 T 의 개수가 최소 하나 이상 존재하는지를 확인한다. 만약 다른 M 이 존재한다면 T 의 개수가 하나 더 필요하므로 구한 개수에서 M 의 개수만큼 빼준 후 확인한다. T 와 M 의 개수를 사전에 구간합으로 구해놓으면 개수를 구하는데 O(1) 시간이 소요되어 총 O(n) 만에 검사할 수 있다.

후기

C번을 풀 시간이 한 시간 이상 남아있었지만 dp 점화식을 끝내 찾지 못했다 :(