A - 321-like Checker (난이도 22)

주어진 숫자의 각 자리를 순차적으로 확인하여 이전 자리보다 현재 자리가 항상 작은지 검사합니다.

void solve() {
    int n;
    cin >> n;
    int prev = -1;
    while (n > 0) {
        int cur = n % 10;
        if (cur <= prev) {
            cout << "No" << endl;
            return;
        }
        prev = cur;
        n /= 10;
    }
    cout << "Yes" << endl;
}

B - Cutoff (난이도 220)

마지막 시험 점수를 0부터 100까지 하나씩 대입하여 총점이 목표 점수 x 이상이 되는 최소값을 찾습니다.

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> scores(n);
    for (int i = 0; i < n - 1; i++) cin >> scores[i];

    for (int last = 0; last <= 100; last++) {
        scores[n-1] = last;
        vector<int> tmp = scores;
        sort(tmp.begin(), tmp.end());
        int sum = 0;
        for (int i = 1; i < n - 1; i++) sum += tmp[i];
        if (sum >= x) {
            cout << last << endl;
            return;
        }
    }
    cout << -1 << endl;
}

C - 321-like Searcher (난이도 591)

가능한 모든 321-like 숫자를 생성한 후 정렬하여 k번째 숫자를 출력합니다.

void solve() {
    int k;
    cin >> k;
    vector<long long> arr;
    for (int bits = 0; bits < (1 << 10); bits++) {
        long long val = 0;
        for (int d = 9; d >= 0; d--) {
            if (bits & (1 << d)) {
                val = val * 10 + d;
            }
        }
        arr.push_back(val);
    }
    sort(arr.begin(), arr.end());
    cout << arr[k + 1] << endl;
}

D - Set Menu (난이도 806)

메인 메뉴를 정렬하고, 각 사이드 메뉴에 대해 가격 합의 상한 p를 고려해 이분 탐색으로 최적의 합을 계산합니다.

void solve() {
    int n, m, p;
    cin >> n >> m >> p;
    vector<int> mainMenu(n), sideMenu(m);
    for (int i = 0; i < n; i++) cin >> mainMenu[i];
    for (int i = 0; i < m; i++) cin >> sideMenu[i];
    sort(mainMenu.begin(), mainMenu.end());

    vector<long long> prefix(n + 1);
    for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + mainMenu[i];

    long long answer = 0;
    for (int side : sideMenu) {
        int idx = lower_bound(mainMenu.begin(), mainMenu.end(), p - side) - mainMenu.begin();
        answer += prefix[idx];
        answer += 1LL * idx * side;
        answer += 1LL * p * (n - idx);
    }
    cout << answer << endl;
}

E - Complete Binary Tree (난이도 1627)

LCA를 기준으로 거리가 k인 노드의 개수를 이분 탐색 형태로 계산합니다.

long long countNodes(long long cur, long long dist) {
    if (cur > n || dist < 0) return 0;
    long long left = cur, right = cur;
    while (dist--) {
        left <<= 1;
        right = (right << 1) | 1;
        if (left > n) return 0;
    }
    if (right <= n) return right - left + 1;
    else return n - left + 1;
}

void solve() {
    cin >> n >> x >> k;
    long long prev = 1LL << 60;
    long long result = 0;
    while (x) {
        result += countNodes(x, k);
        result -= countNodes(prev, k - 1);
        k--;
        prev = x;
        x >>= 1;
    }
    cout << result << endl;
}

F - #(subset sum = K) with Add and Erase (난이도 1645)

기본 배낭 문제에 원소 추가/제거 연산을 처리합니다. 추가 시 역방향 DP, 제거 시 정방향 DP를 적용합니다.

const int MOD = 998244353;
const int MAX_VAL = 5000;
int dp[MAX_VAL + 1];

void solve() {
    int q, k;
    cin >> q >> k;
    dp[0] = 1;
    while (q--) {
        string op;
        int val;
        cin >> op >> val;
        if (op == "+") {
            for (int s = MAX_VAL; s >= val; s--) {
                dp[s] = (dp[s] + dp[s - val]) % MOD;
            }
        } else {
            for (int s = val; s <= MAX_VAL; s++) {
                dp[s] = (dp[s] - dp[s - val] + MOD) % MOD;
            }
        }
        cout << dp[k] << endl;
    }
}

G - Electric Circuit (난이도 2439)

비트마스크 DP를 사용하여 포트 간 연결을 고려한 모든 경우의 수를 계산합니다.

const int N = 17;
int n, m;
int inDeg[N], outDeg[N];
int sumIn[1<<N], sumOut[1<<N];
mint dp[1<<N], ways[1<<N];
mint answer;

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x; cin >> x; x--;
        inDeg[x]++;
    }
    for (int i = 0; i < m; i++) {
        int x; cin >> x; x--;
        outDeg[x]++;
    }

    Factorial fact(m);
    for (int mask = 1; mask < (1<<n); mask++) {
        for (int i = 0; i < n; i++) {
            if (mask & (1<<i)) {
                sumIn[mask] += inDeg[i];
                sumOut[mask] += outDeg[i];
            }
        }
        if (sumIn[mask] != sumOut[mask]) continue;
        dp[mask] = ways[mask] = fact.factorial(sumIn[mask]);

        for (int sub = mask; sub; sub = (sub - 1) & mask) {
            if ((sub & (-mask)) == 0) continue;
            dp[mask] -= dp[sub] * ways[mask ^ sub];
        }
        answer += dp[mask] * fact.factorial(m - sumIn[mask]);
    }
    cout << answer / fact.factorial(m) << endl;
}