[Algorithm] cpp-python 백준 18485번 : Nine Judges

심사위원 선호 순위로 유도된 다수결 비교(토너먼트)에서 해밀토니안 경로를 구성해 상위 p개를 취해 ‘plausible set’을 찾는다. 분할-정복 머지와 다수결 비교로 O(n·k log k), 구현은 pos 테이블로 O(n·k) 메모리. 엣지/동률 없음(다수결 임계), 입력 정합성·인덱스·출력 형식 점검.

1) 문제 정보

문제: https://www.acmicpc.net/problem/18485
요약: n (≤9, 홀수)명의 심사위원이 제시한 k (≤5e4)개 문제의 선호 리스트가 주어진다. 정확히 p개를 뽑아 구성하는 문제셋 S가 무한 반복되는 무작위 교체 절차에서 양의 확률로 무한히 자주 나타날 수(plausible) 있으면 된다. 임의의 하나의 plausible set을 출력하라.
제한/스펙: 시간 2초, 메모리 512MB, n은 작고 k가 크다.

2) 입출력 형식/예제

입력

1
2
n k p
<각 심사위원 i에 대해 길이 k의 순열 a_{i,1..k}>

출력

1
p개의 서로 다른 문제 번호 (1..k), 순서는 임의

예제

3) 접근 개요(아이디어 스케치)

다수결 비교 정의: 문제 x, y에 대해 과반((n+1)/2) 이상의 심사위원이 x를 y 앞에 두면 x > y로 본다. 이는 모든 쌍에서 승패가 정해지는 방향 그래프(토너먼트)를 이룬다.
토너먼트에는 항상 해밀토니안 경로가 존재한다. 이 경로의 앞쪽 문제들은 다수결 관점에서 “강한” 문제들이다.
해밀토니안 경로를 분할정복 머지로 구성한 뒤, 경로의 선두 p개를 답으로 사용하면 해당 집합이 plausible set이 됨이 알려져 있다(이 과정은 관련 캠프/에디토리얼의 고전적 구성).

4) 알고리즘 설계

자료구조:
- pos[judge][problem] = 등수(작을수록 선호) 테이블 (크기 O(n·k)).
- beats(a,b): 과반 심사위원이 a를 b보다 선호하면 true.
해밀토니안 경로 구성(분할정복):
1. 전체 문제 집합을 반으로 쪼개 각각 재귀적으로 경로를 만든다.
2. 두 경로를 병합할 때, 머지 과정에서 현재 두 후보 L[i], R[j]를 비교하여 beats(L[i], R[j])면 L[i]를, 아니면 R[j]를 결과에 추가한다.
3. 최종 경로 order를 얻는다.
답 구성: order의 앞쪽 p개 문제 번호를 출력.

올바름(핵심 근거):

토너먼트에서 분할정복-머지 방식은 해밀토니안 경로를 생성한다(머지 중 항상 하나가 다수결에서 우세이므로 진행 가능).
생성된 경로의 선두 p개는 무작위 교체 프로세스에서 양의 정적분 확률로 반복 출현하는 plausible set이 됨이 알려져 있다(관련 대회/에디토리얼 정리).

5) 복잡도

시간: O(k log k)번 비교 × 비교당 O(n) → O(n · k log k)
공간: O(n · k) (선호 순위 테이블) + O(k) (재귀/머지 보조 배열)

6) 구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

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

    int n, k, p;
    if (!(cin >> n >> k >> p)) return 0;

    vector<vector<int>> pos(n, vector<int>(k + 1));
    for (int j = 0; j < n; ++j) {
        for (int r = 1; r <= k; ++r) {
            int id; cin >> id;
            pos[j][id] = r;
        }
    }

    const int maj = (n / 2) + 1;
    auto beats = [&](int a, int b) -> bool {
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            if (pos[j][a] < pos[j][b]) {
                if (++cnt >= maj) return true;
            }
        }
        return false;
    };

    function<vector<int>(const vector<int>&)> build = [&](const vector<int>& v) -> vector<int> {
        if (v.size() <= 1) return v;
        size_t mid = v.size() / 2;
        vector<int> L(v.begin(), v.begin() + mid);
        vector<int> R(v.begin() + mid, v.end());
        L = build(L);
        R = build(R);
        vector<int> res; res.reserve(v.size());
        size_t i = 0, j = 0;
        while (i < L.size() && j < R.size()) {
            if (beats(L[i], R[j])) res.push_back(L[i++]);
            else res.push_back(R[j++]);
        }
        while (i < L.size()) res.push_back(L[i++]);
        while (j < R.size()) res.push_back(R[j++]);
        return res;
    };

    vector<int> all(k); iota(all.begin(), all.end(), 1);
    vector<int> order = build(all);
    for (int i = 0; i < p; ++i) {
        if (i) cout << ' ';
        cout << order[i];
    }
    cout << '\n';
    return 0;
}

6-1) 구현 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

def solve():
    n, k, p = map(int, input().split())
    pos = [[0]*(k+1) for _ in range(n)]
    for j in range(n):
        arr = list(map(int, input().split()))
        for r, pid in enumerate(arr, 1):
            pos[j][pid] = r

    maj = (n // 2) + 1

    def beats(a: int, b: int) -> bool:
        cnt = 0
        for j in range(n):
            if pos[j][a] < pos[j][b]:
                cnt += 1
                if cnt >= maj:
                    return True
        return False

    def build(v):
        if len(v) <= 1:
            return v
        mid = len(v) // 2
        L = build(v[:mid])
        R = build(v[mid:])
        res = []
        i = j = 0
        while i < len(L) and j < len(R):
            if beats(L[i], R[j]):
                res.append(L[i]); i += 1
            else:
                res.append(R[j]); j += 1
        if i < len(L):
            res.extend(L[i:])
        if j < len(R):
            res.extend(R[j:])
        return res

    order = build(list(range(1, k+1)))
    print(*order[:p])

if __name__ == "__main__":
    solve()