Educational Codeforces Round 114 (Rated for Div. 2) A, B

A. Regular Bracket Sequences

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
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int n;

void solve(int o, int c, string &s, vector<string> &ans){
    // 기저 사례
    if(s.size() == 2*n){
        ans.push_back(s);
        return;
    }
    if(ans.size() == n) return;
    // 재귀 호출
    if(o > c){
        s = s + ")";
        solve(o, c+1, s, ans);
        s.pop_back();
    }
    if(o < n){
        s = s + "(";
        solve(o+1, c, s, ans);
        s.pop_back();
    }
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        vector<string> ans;
        string s = "(";
        solve(1, 0, s, ans);
        for(auto i : ans) cout << i << "\n";
    }
    return 0;
}

n 값에 따라 Regular 한 괄호의 조합은 무수히 많지만 그 중 n 개만을 출력하는 문제이기 때문에, n 개의 정답을 출력할 때 까지만 모든 경우의 수를 조사해주면 된다.

B. Combinatorics Homework

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
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int v[3];
        for(int& i : v) cin >> i;
        int m;
        cin >> m;
        int p = 0;
        int ma = 0;
        int sum = 0;
        for(int i : v){
            if(i >= 2) p += i-1;
            ma = max(ma, i);
            sum += i;
        }
        int other = sum-ma;
        if(ma-other-1 <= m && m <= p) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

완전 탐색으로 작은 예제의 모든 조합을 확인해보고 규칙성을 찾아 풀이했다.

최소 m 값은 a, b, c 값 중 제일 큰 값에서 나머지 두 값을 뺀 결과에 -1 한 값이 되고, 최대 m 값은 a, b, c 값이 섞이지 않고 나열되었을 때 쌍의 개수가 된다.

주어진 m 값이 범위 내에 포함되는지를 확인하여 YES 또는 NO 를 출력한다.

---

C. Slay the Dragon (Upsolving)

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
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

bool compare(ll a, ll b){
    return a < b;
}

int main(){
    fastio;
    int n;
    cin >> n;
    vector<ll> a(n);
    ll strength = 0;
    for(auto& i : a){
        cin >> i;
        strength += i;
    }
    sort(all(a), compare);
    int m;
    cin >> m;
    vector<ll> x(m), y(m);
    for(int i = 0; i < m; i++){
        cin >> x[i] >> y[i];
    }
    for(int i = 0; i < m; i++){
        ll ans = 0;
        auto iter = lower_bound(all(a), x[i]);
        if(iter == a.begin()){
            ll go = *iter;
            ll defense = strength-go;
            if(go < x[i]) ans += x[i]-go;
            if(defense < y[i]) ans += y[i]-defense;
        }
        else if(iter == a.end()){
            ll go = *--iter;
            ll defense = strength-go;
            if(go < x[i]) ans += x[i]-go;
            if(defense < y[i]) ans += y[i]-defense;
        }
        else{
            ll go1 = *iter;
            ll defense1 = strength-go1;
            ll ans1 = 0;
            if(go1 < x[i]) ans1 += x[i]-go1;
            if(defense1 < y[i]) ans1 += y[i]-defense1;
            ll go2 = *--iter;
            ll defense2 = strength-go2;
            ll ans2 = 0;
            if(go2 < x[i]) ans2 += x[i]-go2;
            if(defense2 < y[i]) ans2 += y[i]-defense2;
            ans = min(ans1, ans2);
        }
        cout << ans << "\n";
    }
    return 0;
}

솔루션은 찾았지만 A, B 에서 시간을 너무 오래써서 풀지 못했던 문제.

금화를 최대한 적게 사용하면서 용을 죽이기 위해 어떤 영웅을 내보내야 할지 빠르게 결정해야한다.

용의 방어력과 인접한 공격력을 가진 영웅을 내보낼 때가 최적의 경우이므로, 영웅 힘 배열 a 를 오름차순 정렬한 뒤 이진 탐색으로 용의 방어력보다 작거나 같은 또는 높은 공격력을 가진 영웅 둘을 후보로 삼고 필요한 금화의 개수를 계산하면 된다.

용의 방어력이 모든 영웅의 공격력보다 작거나 같고, 높거나 같은 경우는 정답이 유일하므로 비교없이 계산하여 출력해준다.