Problem A: Drinks Choosing

N명의 학생들이 각자 선호하는 음료 맛이 있습니다. 총 $\lceil n/2 \rceil$개의 세트가 제공되며, 각 세트에는 같은 맛의 음료 2병이 들어 있습니다. 목표는 최대한 많은 학생이 자신이 원하는 맛의 음료를 받을 수 있도록 배분하는 것입니다.

가장 효율적인 방법은 동일한 맛을 원하는 학생들을 2명씩 묶어 한 세트를 주는 것입니다. 이렇게 짝을 지어 배분한 뒤 남은 세트들은 각각 한 명씩의 요구사항만 충족시킬 수 있습니다. 즉, 각 맛의 빈도수를 계산하여 짝수 명의 그룹을 먼저 처리하고, 남은 홀수 명의 인원들은 남은 세트 수만큼 추가로 만족시킬 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int student_count, flavor_limit;
    cin >> student_count >> flavor_limit;

    vector<int> counts(flavor_limit + 1, 0);
    for (int i = 0; i < student_count; ++i) {
        int favorite;
        cin >> favorite;
        counts[favorite]++;
    }

    int satisfied = 0;
    int remaining_odds = 0;
    int total_sets = (student_count + 1) / 2;

    for (int i = 1; i <= flavor_limit; ++i) {
        satisfied += (counts[i] / 2) * 2;
        total_sets -= counts[i] / 2;
        if (counts[i] % 2 == 1) {
            remaining_odds++;
        }
    }

    satisfied += total_sets;
    cout << satisfied << endl;

    return 0;
}

Problem B: Sport Mafia

사탕 상자에 두 가지 작업을 수행할 수 있습니다. 첫 번째 작업은 사탕을 추가하는 것인데, 이전에 추가한 개수보다 1개 더 많이 넣습니다(1, 2, 3... 순서). 두 번째 작업은 사탕을 1개 꺼내는 것입니다. 총 $n$번의 작업을 수행한 후 상자에 $k$개의 사탕이 남았을 때, 사탕을 꺼낸 횟수를 구해야 합니다.

사탕을 추가한 횟수를 $x$라고 가정하면, 꺼낸 횟수는 $n - x$가 됩니다. 추가된 총 사탕의 개수는 등차수열의 합 공식에 의해 $x(x+1)/2$입니다. 따라서 최종 사탕 개수 $k$는 다음과 같은 방정식으로 나타낼 수 있습니다: $x(x+1)/2 - (n - x) = k$. 이 방정식에서 $x$를 구하기 위해 이분 탐색을 활용하거나 근의 공식을 사용할 수 있습니다.

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    ll n, k;
    cin >> n >> k;

    ll low = 0, high = n, put_count = 0;
    while (low <= high) {
        ll mid = (low + high) / 2;
        ll current_candies = mid * (mid + 1) / 2 - (n - mid);
        if (current_candies == k) {
            put_count = mid;
            break;
        } else if (current_candies < k) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << n - put_count << endl;
    return 0;
}

Problem C: Basketball Exercise

2행 $n$열로 배치된 학생들 중에서 합산 키가 최대가 되도록 팀을 구성해야 합니다. 선택 시 두 가지 제약 조건이 있습니다. 첫째, 동일한 열(column)에서는 최대 한 명만 선택할 수 있습니다. 둘째, 바로 직전 열에서 선택한 행(row)과 같은 행에 있는 학생은 연속해서 선택할 수 없습니다.

이 문제는 다이나믹 프로그래밍(DP)으로 해결할 수 있습니다. 각 열 $i$에 대해 세 가지 상태를 정의합니다.

• $dp[i][0]$: $i$번째 열에서 1행 학생을 선택한 경우의 최대 합
• $dp[i][1]$: $i$번째 열에서 2행 학생을 선택한 경우의 최대 합
• $dp[i][2]$: $i$번째 열에서 아무도 선택하지 않은 경우의 최대 합

점화식은 직전 열의 서로 다른 행을 선택했거나 건너뛴 경우 중 최댓값을 취하는 방식으로 구성됩니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;

    vector<ll> row1(n), row2(n);
    for (int i = 0; i < n; ++i) cin >> row1[i];
    for (int i = 0; i < n; ++i) cin >> row2[i];

    vector<vector<ll>> dp(n, vector<ll>(3, 0));
    dp[0][0] = row1[0];
    dp[0][1] = row2[0];
    dp[0][2] = 0;

    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + row1[i];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + row2[i];
        dp[i][2] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
    }

    cout << max({dp[n-1][0], dp[n-1][1], dp[n-1][2]}) << endl;
    return 0;
}

Problem D: Submarine in the Rybinsk Sea

두 숫자 $a$와 $b$를 섞는 함수 $f(a, b)$는 $b$의 마지막 자리, $a$의 마지막 자리 순으로 번갈아 가며 배치하여 새로운 숫자를 만듭니다. 배열 내의 모든 쌍 $(i, j)$에 대해 $f(a_i, a_j)$의 합을 998,244,353으로 나눈 나머지를 구하는 문제입니다.

핵심은 각 숫자의 각 자릿수가 결과값에 기여하는 정도를 개별적으로 계산하는 것입니다. 어떤 숫자 $a_i$의 $k$번째 자릿수가 $f(a_i, a_j)$에서 어느 위치에 오게 될지는 $a_j$의 길이에 따라 결정됩니다. 배열 내 숫자들의 길이 분포를 미리 파악한 뒤, 각 자릿수마다 가능한 모든 길이에 대한 기여도를 합산하면 $O(N \cdot \text{max\_digit})$의 시간 복잡도로 해결 가능합니다.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
const int MOD = 998244353;

ll powers[25];

void precompute_powers() {
    powers[0] = 1;
    for (int i = 1; i < 25; ++i) powers[i] = (powers[i - 1] * 10) % MOD;
}

int main() {
    int n;
    cin >> n;
    vector<ll> nums(n);
    vector<int> len_counts(11, 0);

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        int temp = nums[i], cur_len = 0;
        while (temp) { cur_len++; temp /= 10; }
        len_counts[cur_len]++;
    }

    precompute_powers();
    ll total_sum = 0;

    for (int i = 0; i < n; ++i) {
        for (int L = 1; L <= 10; ++L) {
            if (len_counts[L] == 0) continue;
            
            ll val = nums[i];
            ll contrib_a = 0, contrib_b = 0;
            int pos = 0;
            
            while (val > 0) {
                int digit = val % 10;
                val /= 10;
                
                if (pos < L) {
                    contrib_a = (contrib_a + (ll)digit * powers[2 * pos + 1]) % MOD;
                    contrib_b = (contrib_b + (ll)digit * powers[2 * pos]) % MOD;
                } else {
                    contrib_a = (contrib_a + (ll)digit * powers[pos + L]) % MOD;
                    contrib_b = (contrib_b + (ll)digit * powers[pos + L]) % MOD;
                }
                pos++;
            }
            total_sum = (total_sum + (contrib_a + contrib_b) * len_counts[L]) % MOD;
        }
    }

    cout << total_sum << endl;
    return 0;
}

Problem E: OpenStreetMap

주어진 점화식으로 $n \times m$ 크기의 행렬을 생성하고, 모든 $a \times b$ 크기의 부분 행렬 내 최솟값들의 총합을 구해야 합니다. 행렬의 크기가 최대 $3000 \times 3000$이므로 효율적인 2차원 범위 최솟값 쿼리(Range Minimum Query) 알고리즘이 필요합니다.

단조 큐(Monotonic Queue)를 사용하여 슬라이딩 윈도우 최솟값을 구하는 방식을 적용합니다. 먼저 각 행에 대해 길이가 $b$인 윈도우의 최솟값을 모두 구하여 새로운 행렬을 만듭니다. 그 다음, 생성된 행렬의 각 열에 대해 길이가 $a$인 윈도우의 최솟값을 구하면 각 $a \times b$ 부분 행렬의 최솟값을 $O(NM)$ 시간에 모두 찾을 수 있습니다.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

typedef long long ll;

int main() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    ll g, x, y, z;
    cin >> g >> x >> y >> z;

    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            grid[i][j] = g;
            g = (g * x + y) % z;
        }
    }

    vector<vector<int>> row_min(n, vector<int>(m - b + 1));
    for (int i = 0; i < n; ++i) {
        deque<int> dq;
        for (int j = 0; j < m; ++j) {
            while (!dq.empty() && grid[i][dq.back()] >= grid[i][j]) dq.pop_back();
            dq.push_back(j);
            if (dq.front() <= j - b) dq.pop_front();
            if (j >= b - 1) row_min[i][j - b + 1] = grid[i][dq.front()];
        }
    }

    ll ans = 0;
    int new_m = m - b + 1;
    for (int j = 0; j < new_m; ++j) {
        deque<int> dq;
        for (int i = 0; i < n; ++i) {
            while (!dq.empty() && row_min[dq.back()][j] >= row_min[i][j]) dq.pop_back();
            dq.push_back(i);
            if (dq.front() <= i - a) dq.pop_front();
            if (i >= a - 1) ans += row_min[dq.front()][j];
        }
    }

    cout << ans << endl;
    return 0;
}