A - 손 소독하기

N명의 외계인이 순차적으로 손을 소독하려고 합니다. 각 외계인은 H_i개의 손을 가지고 있으며, 전체를 소독해야 합니다. 소독제는 총 M회 사용할 수 있습니다. 한 외계인이 소독을 할 때 필요한 양만큼만 사용하며, 부족하면 남은 양만 소모합니다. 모든 손을 소독한 외계인의 수를 구하세요.

단순히 앞에서부터 순회하면서 소독제 잔량을 갱신하고, 소진되기 전까지 카운트를 증가시키면 됩니다.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int count = 0;
    for (int i = 0; i < n; ++i) {
        int hands;
        cin >> hands;
        if (m >= hands) {
            count++;
            m -= hands;
        } else {
            m = 0;
        }
    }
    cout << count;
    return 0;
}

B - 대소문자 변환

영문자로 구성된 문자열 S가 주어집니다. 문자열 길이는 홀수입니다. 대문자의 개수가 소문자보다 많으면 전체를 대문자로, 그렇지 않으면 전체를 소문자로 변환하여 출력하세요.

각 문자를 순회하며 대소문자 개수를 세고, 조건에 따라 변환 여부를 결정합니다.

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int lower = 0, upper = 0;
    for (char c : s) {
        if (islower(c)) lower++;
        else upper++;
    }
    for (char c : s) {
        if (lower > upper) {
            cout << (char)tolower(c);
        } else {
            cout << (char)toupper(c);
        }
    }
    return 0;
}

C - 시에르핀스키 카펫

K차 시에르핀스키 카펫은 다음과 같이 정의됩니다:

• K=0: 1×1 검은색 격자
• K≥1: 3^K × 3^K 격자를 9등분했을 때, 중앙은 모두 흰색이고 나머지 8개 블록은 (K-1)차 카펫입니다.

N이 주어질 때, N차 카펫을 출력하세요.

반복적으로 확장하는 방식으로 구현할 수 있습니다. 초기 3×3 패턴에서 시작해, 단계별로 크기를 3배 늘리며 중앙을 제외한 블록을 복사합니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> carpet = {"###", "#.#", "###"};
    
    for (int k = 1; k <= n; ++k) {
        vector<string> next(3 * carpet.size(), string(3 * carpet[0].size(), '.'));
        int block = carpet.size();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (i == 1 && j == 1) continue;
                for (int x = 0; x < block; ++x) {
                    for (int y = 0; y < block; ++y) {
                        next[i*block + x][j*block + y] = carpet[x][y];
                    }
                }
            }
        }
        carpet = move(next);
    }
    
    for (const auto& row : carpet) {
        cout << row << '\n';
    }
    return 0;
}

D - 반복 숫자 나머지 계산

V_N은 숫자 N을 N번 이어붙인 정수입니다. 예를 들어 V_3 = 333, V_10 = 1010...10 (10번). V_N mod 998244353을 구하세요.

V_N은 등비수열 합으로 표현할 수 있습니다. N이 d자릿수일 때, V_N = N × (10^{d×N} - 1) / (10^d - 1). 모듈러 역원과 빠른 거듭제곱을 이용해 계산합니다. 지수 부분은 오일러 정리에 따라 mod-1로 축소합니다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

ll powmod(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    string num;
    cin >> num;
    ll n = 0, len = num.size();
    ll power = 1;
    for (char c : num) {
        n = (n * 10 + (c - '0')) % MOD;
        power = power * 10 % MOD;
    }
    
    ll numerator = (powmod(power, n % (MOD-1), MOD) - 1 + MOD) % MOD;
    numerator = numerator * n % MOD;
    ll denominator = (power - 1 + MOD) % MOD;
    ll inv_denom = powmod(denominator, MOD-2, MOD);
    cout << numerator * inv_denom % MOD;
    return 0;
}

E - 기능 그래프 도달 가능성

N개의 정점이 있고, 각 정점 i는 a_i로 가는 유일한 간선을 가집니다. 이때, u에서 v로 도달 가능한 쌍 (u,v)의 수를 구하세요.

이 구조는 여러 개의 사이클과 그에 붙은 트리(기저 고리 나무)로 구성됩니다. 먼저 DFS를 통해 사이클을 탐지하고, 사이클 내 정점들은 서로 도달 가능하므로 각각 사이클 크기만큼 기여합니다. 트리 부분은 위상 정렬이나 메모이제이션으로 처리하며, 각 노드는 자식의 값 + 1을 갖습니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> to(n+1), visited(n+1), value(n+1);
    for (int i = 1; i <= n; ++i) cin >> to[i];

    for (int i = 1; i <= n; ++i) {
        if (visited[i]) continue;
        int cur = i;
        while (!visited[cur]) {
            visited[cur] = i;
            cur = to[cur];
        }
        if (visited[cur] == i) { // 새로운 사이클 발견
            vector<int> cycle;
            int node = cur;
            do {
                cycle.push_back(node);
                node = to[node];
            } while (node != cur);
            for (int v : cycle) value[v] = cycle.size();
        }
    }

    function<int(int)> dfs = [&](int u) -> int {
        if (value[u]) return value[u];
        return value[u] = dfs(to[u]) + 1;
    };

    ll total = 0;
    for (int i = 1; i <= n; ++i) total += dfs(i);
    cout << total;
    return 0;
}

F - 두 수열 쿼리

두 수열 A와 B가 주어지고, 다음 세 가지 쿼리를 처리하세요:

• 1 l r x: A[l..r]에 x 더하기
• 2 l r x: B[l..r]에 x 더하기
• 3 l r: Σ(A_i × B_i) mod 998244353

세그먼트 트리를 사용하며, 각 노드는 ΣA, ΣB, Σ(A×B) 값을 저장합니다. 레이지 프로퍼게이션으로 두 가지 업데이트를 관리합니다. A에 k를 더하면 Σ(A×B)는 k × ΣB만큼 증가하며, B에 대해서도 마찬가지입니다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int MAX = 2e5+5;
const ll MOD = 998244353;

struct Node {
    ll sum_a, sum_b, sum_ab, lazy_a, lazy_b;
} tree[MAX << 2];

void pushup(int u) {
    tree[u].sum_a = (tree[u<<1].sum_a + tree[u<<1|1].sum_a) % MOD;
    tree[u].sum_b = (tree[u<<1].sum_b + tree[u<<1|1].sum_b) % MOD;
    tree[u].sum_ab = (tree[u<<1].sum_ab + tree[u<<1|1].sum_ab) % MOD;
}

void apply(int u, int l, int r, ll add_a, ll add_b) {
    int len = r - l + 1;
    tree[u].sum_ab = (tree[u].sum_ab + add_a * tree[u].sum_b % MOD + 
                      add_b * tree[u].sum_a % MOD + add_a * add_b % MOD * len) % MOD;
    tree[u].sum_a = (tree[u].sum_a + add_a * len) % MOD;
    tree[u].sum_b = (tree[u].sum_b + add_b * len) % MOD;
    tree[u].lazy_a = (tree[u].lazy_a + add_a) % MOD;
    tree[u].lazy_b = (tree[u].lazy_b + add_b) % MOD;
}

void pushdown(int u, int l, int r) {
    if (tree[u].lazy_a == 0 && tree[u].lazy_b == 0) return;
    int mid = (l + r) >> 1;
    apply(u<<1, l, mid, tree[u].lazy_a, tree[u].lazy_b);
    apply(u<<1|1, mid+1, r, tree[u].lazy_a, tree[u].lazy_b);
    tree[u].lazy_a = tree[u].lazy_b = 0;
}

void build(int u, int l, int r, vector<ll>& A, vector<ll>& B) {
    if (l == r) {
        tree[u] = {A[l], B[l], (A[l]*B[l])%MOD, 0, 0};
    } else {
        int mid = (l + r) >> 1;
        build(u<<1, l, mid, A, B);
        build(u<<1|1, mid+1, r, A, B);
        pushup(u);
    }
}

void update(int u, int l, int r, int ul, int ur, ll add_a, ll add_b) {
    if (ul <= l && r <= ur) {
        apply(u, l, r, add_a, add_b);
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (ul <= mid) update(u<<1, l, mid, ul, ur, add_a, add_b);
    if (ur > mid) update(u<<1|1, mid+1, r, ul, ur, add_a, add_b);
    pushup(u);
}

ll query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[u].sum_ab;
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid) res = (res + query(u<<1, l, mid, ql, qr)) % MOD;
    if (qr > mid) res = (res + query(u<<1|1, mid+1, r, ql, qr)) % MOD;
    return res;
}