T1: 중위값이 특정 값인 홀수 길이 부분 배열 개수 세기

주어진 순열에서 특정 수 ( b )를 중위값으로 가지는 홀수 길이의 부분 배열의 수를 구하는 문제이다.

핵심 아이디어는 각 원소를 ( b )보다 작으면 -1, 크면 1, 같으면 0으로 변환한 후, 누적합을 이용해 조건을 만족하는 쌍을 찾는 것이다. ( b )의 위치를 기준으로 오른쪽은 해시맵에 누적합을 저장하고, 왼쪽에서는 해당 누적합과 일치하는 값을 찾아 매칭한다.

이는 중위값 조건을 "왼쪽과 오른쪽의 상대적인 개수 차이"로 변환하여 해결할 수 있다.

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;

int n, target;
int arr[200010];
map<int, int> prefixCount;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> target;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        if (arr[i] < target) arr[i] = -1;
        else if (arr[i] > target) arr[i] = 1;
        else arr[i] = 0;
    }

    // 누적합 계산
    for (int i = 1; i <= n; ++i) {
        arr[i] += arr[i-1];
    }

    long long result = 0;
    int pivot = 0;
    for (int i = 1; i <= n; ++i) {
        if (arr[i] == 0) {
            pivot = i;
            break;
        }
    }

    // 오른쪽 누적합 저장
    for (int i = pivot; i <= n; ++i) {
        prefixCount[arr[i]]++;
    }

    // 왼쪽에서 매칭
    for (int i = 1; i <= pivot; ++i) {
        result += prefixCount[arr[i-1]];
    }

    cout << result << '\n';

#ifndef ONLINE_JUDGE
    cerr << "\nUsed time: " << clock() * 1.0 / CLOCKS_PER_SEC << "s.\n";
#endif
    return 0;
}

T2: 이진수 표현에서 최대 비트 차이 구하기

각 원소 ( a_i )에 대해, 다른 원소와의 비트 차이가 가장 큰 값을 찾는 문제다. 비트 차이란 두 수의 비트가 다를 자리 수를 의미하며, 이는 ( a_i \oplus a_j )의 비트 개수와 같다.

문제는 모든 ( a_i )에 대해 최대 ( \text{popcount}(a_i \oplus a_j) )를 구하는 것이다.

효율적으로 접근하려면, 모든 수를 기준으로 1비트씩 변경하면서 가능한 모든 상태를 BFS로 탐색한다. 이 과정에서 각 상태까지의 최단 거리를 저장하면, ( d[x] )는 ( x )와 원래 집합 내 수 사이의 최소 비트 차이를 의미한다. 따라서 ( \text{max_diff} = m - d[\text{flip}(a_i)] )로 계산 가능하다.

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;

int n, bits;
int nums[1048577];
bool visited[1048577];
int dist[1048577];
queue<int> q;

void bfs() {
    for (int i = 1; i <= n; ++i) {
        q.push(nums[i]);
        visited[nums[i]] = true;
        dist[nums[i]] = 0;
    }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int bit = 0; bit < bits; ++bit) {
            int v = u ^ (1 << bit);
            if (visited[v]) continue;
            visited[v] = true;
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> bits;
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }

    bfs();

    for (int i = 1; i <= n; ++i) {
        int flipped = nums[i] ^ ((1 << bits) - 1);
        cout << bits - dist[flipped] << ' ';
    }
    cout << '\n';

#ifndef ONLINE_JUDGE
    cerr << "\nUsed time: " << clock() * 1.0 / CLOCKS_PER_SEC << "s.\n";
#endif
    return 0;
}

T3: 조합 합산 문제 – 경로 수 세기

두 배열 ( a, b )가 주어질 때, 다음 식의 값을 ( 998244853 )으로 나눈 나머지로 구한다:

[ \sum_{i=1}^{n} \sum_{j=1}^{i-1} \binom{a_i + a_j + b_i + b_j}{a_i + a_j} ]

조합의 의미를 해석하면, ( (0,0) )에서 ( (a_i+a_j, b_i+b_j) )까지 오직 오른쪽과 위로만 이동하는 경로 수이다. 이를 좌표 평행 이동하여 ( (-a_i, -b_i) )에서 ( (a_j, b_j) )로 이동하는 경로로 바꾼다.

모든 시작점 ( (-a_i, -b_i) )에 1을 더한 후, 격자에서 동적계획법을 통해 모든 점까지 도달하는 경로 수를 계산한다. 결과는 모든 ( (a_i, b_i) ) 위치의 경로 수의 합에서 자기 자신에서 자기 자신으로 가는 경우를 제외하고, 중복 계산된 쌍을 반으로 나누어 처리한다.

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
using namespace std;

const long long mod = 998244853;

long long modPow(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

long long fac[200010];
long long comb(long long n, long long m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * modPow(fac[n - m] * fac[m] % mod, mod - 2) % mod;
}

int n;
int a[200010], b[200010];
int dp[5010][5010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        dp[2500 - a[i]][2500 - b[i]]++;
    }

    fac[0] = 1;
    for (int i = 1; i <= 200000; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }

    for (int i = 1; i < 5000; ++i) {
        for (int j = 1; j < 5000; ++j) {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i][j]) % mod;
        }
    }

    long long total = 0;
    for (int i = 1; i <= n; ++i) {
        long long pathCount = dp[2500 + a[i]][2500 + b[i]];
        long long selfPath = comb(2 * (a[i] + b[i]), 2 * a[i]);
        total = (total + pathCount - selfPath + mod) % mod;
    }

    cout << total * modPow(2, mod - 2) % mod << '\n';

#ifndef ONLINE_JUDGE
    cerr << "\nUsed time: " << clock() * 1.0 / CLOCKS_PER_SEC << "s.\n";
#endif
    return 0;
}

결론

T3, T4는 복잡도와 개념적 깊이가 깊어 실전에서 쉽게 접근하기 어려웠다. 특히 T3는 조합의 기하학적 해석과 격자 동적계획법의 통합이 요구되며, 부분합과 중복 제거 전략이 정교하게 필요했다.