본문 바로가기

알고리즘 문제풀이

SCPC 2020 1차예선 풀이, 후기

올해 SCPC는 작년보다 푸는 시간이 더 빨라진 것 같다!

알고리즘에 따라 나누어 보면 1번 그리디, 2번 DP, 3번 DP, 4번 세그먼트 트리, 5번 기하가 출제되었다.

 

구현 소스 코드 링크: 1번, 2번, 3번, 4번(별도의 글), 5번(별도의 글)

문제 1. 다이어트

설명

길이 \(N\)인 두 수열 \(A[1..N]\), \(B[1..N]\)이 주어져 있을 때, 두 수열에서 숫자를 각각 하나씩 뽑아 순서쌍 \((A[i], B[j])\)를 만드는 작업을 \(K\)번 반복하였다. 만들어진 \(K\)개의 순서쌍에서 두 수의 합의 최댓값을 최소화하도록 순서쌍들을 뽑으면 그 값은 얼마인가? (단, 한 번 쓴 수는 다시 쓰지 않는다.)

 

제한조건: \(1 \le N \le 200,000\), \(1 \le K \le N\)

실행조건: 10개 이하 테스트 케이스에 대한 실행시간 총합 2초 이내

풀이

그리디 알고리즘을 적용할 수 있다. 우선 수열에서 수가 주어진 순서는 상관이 없으므로, 오름차순으로 정렬하고 보자. 그러면 \(A\)와 \(B\)에서 각각 가장 작은 \(K\)개의 수를 사용하는 최적해가 있다. 그렇지 않다면, 그 밖에서 사용된 어떤 수 \(x\)가 있고, 같은 수열에는 가장 작은 \(K\)개의 수 중 사용되지 않은 것 \(y\)가 있으므로, 둘을 바꾸면 해당 순서쌍의 두 수의 합은 같거나 감소한다. 따라서 목적함수를 더 나빠지게 하지 않으면서 가장 작은 \(K\)개의 수를 사용하게 만들 수 있다.

 

그러면 \(A\)와 \(B\)에서 뽑은 각 \(K\)개의 수들을 어떻게 배치할 수 있을까? 2행 \(K\)열 표에, 1행에 \(A[1..K]\)를 순서대로 적고 \(B\)의 수를 배치해보자. \(B[K]\)는 반드시 \(A[1]\)과 매칭되어야 한다. 그렇지 않다면, \(A[1]\)은 \(B[j]\) \((j \neq K)\)와, \(B[K]\)는 \(A[i]\) \((i \neq 1)\)와 매칭되어 있다. 즉, (A[1], B[j]), (A[i], B[K])인데, 여기서 가장 큰 합은 A[i] + B[K]이다. 반면 (A[1], B[K]), (A[i], B[j])에서 가장 큰 합은 A[i] + B[j]와 A[1] + B[K] 중 어느 것일 수 있지만, 둘 다 A[i] + B[K]보다는 작거나 같다. 따라서 목적함수를 더 나빠지게 하지 않으면서 A[1]과 B[K]를 매칭하는 최적해가 존재한다.

 

남은 수들(\(A[2..K]\) 및 \(B[1..K-1]\))에 대해서도 그리디 알고리즘이 적용되므로, 동일한 방식으로 매칭하면 된다. 즉, A[1..K]와 B[1..K]를 역순으로 매칭한 후 그 중 최댓값을 계산하면 그것이 구하는 값이 된다.

소스 코드

더보기
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
58
59
60
61
62
63
64
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <queue>
#include <math.h>
#include <memory.h>
 
 
int readInt();
 
 
int N, K;
int A[200000], B[200000];
 
void GatherInput() {
    N = readInt();
    K = readInt();
    for (int i = 0; i < N; i++) {
        A[i] = readInt();
    }
    for (int i = 0; i < N; i++) {
        B[i] = readInt();
    }
}
 
 
void Solve() {
    std::sort(A, A + N);
    std::sort(B, B + N);
 
    int opt = 0;
    for (int i = 0; i < K; i++) {
        int val = A[i] + B[K - 1 - i];
        opt = std::max(opt, val);
    }
    printf("%d\n", opt);
}
 
 
int main() {
    int T = readInt();
    setbuf(stdout, NULL);
 
    for (int test_case = 1; test_case <= T; test_case++) {
        GatherInput();
        printf("Case #%d\n", test_case);
        Solve();
    }
    return 0;
}
 
int readInt() {
    int p;
    scanf("%d"&p);
    return p;
}
 
cs

문제 2. 카드 게임

설명

\(N\)개의 카드가 쌓여있는 두 덱 X, Y가 있다. 각 카드에는 1 이상 K 이하인 정수가 적혀있다.

두 플레이어가 게임을 한다. 각자의 턴에서, 플레이어는 한 덱을 고르고, 그 덱의 윗부분부터 몇 개의 카드를 가져간다. 이때 반드시 하나 이상을 가져가야 하며, 윗부분에서 순서대로 가져가야 하되, 가져가는 카드에 적힌 수의 합이 K를 넘을 수 없다. 마지막으로 카드를 가져가는 사람이 진다.

 

게임 상태는 두 덱 X, Y에 남아있는 카드의 수 \((i, j)\)로 표현할 수 있다. 총 가능한 상태수는 \((N+1)^2\)이다.

플레이어가 자기 턴에 게임 상태 \((i, j)\)를 받았다면, 쌍방 최선의 플레이를 가정했을 때 반드시 지거나 반드시 이긴다.

모든 게임 상태 중 반드시 이기는 상태와 반드시 지는 상태의 가짓수를 각각 계산하면 얼마인가?

 

* 상태 \((0,0)\)은 이긴 상태로 본다.

 

제한조건: \(1 \le N, K \le 3,000\)

실행조건: 50개 이하 테스트 케이스에 대한 실행시간 총합 3초 이내

풀이

DP 문제이다. 내가 상태 \((i, j)\)를 받았다면, 나는 덱 X에서 카드를 가져가거나 덱 Y에서 카드를 가져간다. 따라서, 취할 수 있는 각각의 행동에 대해, 그 행동을 하고 났을 때 상대 플레이어에게 돌아가는 상태를 \((i^\prime, j^\prime)\)이라 하면, 그 상태의 승패 여부를 \(DP[i^\prime][j^\prime]\)에서 읽어서 반대로 취하면 된다. 즉, 만약 모든 가능한 \((i^\prime, j^\prime)\)에 대해 \(DP[i^\prime][j^\prime]\)을 조사했는데 전부 이기는 것으로 되어 있으면 나는 지고, 하나라도 지는 것이 있으면 나는 이긴다. 이때 고려할 \(i^\prime\), \(j^\prime\)은 언제나 각각 \(i\), \(j\)보다 작거나 같고, 반드시 \(i^\prime < i\) 혹은 \(j^\prime < j\)이므로, DP표를 작은 것부터 채우면 순서가 알맞다.

 

이렇게 DP를 구현하면 한 번에 가져갈 수 있는 카드 수가 최대 \(O(N)\)이므로 \(O(N^2)\)개의 상태에 대해 상태전이를 계산하려면 총 \(O(N^3)\)이 든다. 부분문제 1은 \(N \le 200\)이므로 해결이 가능하지만 전체 문제는 안 된다.

 

따라서 상태전이를 최적화해야 한다. 우리는 DP표에서 반드시 연속된 값을 읽는다. 그 값은 해당 칸이 기록된 이후에 절대 변하지 않는다. 따라서 Prefix Sum을 이용할 수 있다. 그러면 상태전이 한 번이 \(O(1)\)에 가능하고, 총 시간은 \(O(N^2)\)이다.

 

* 게임 상태는 두 플레이어에 대해 대칭적이므로 하나의 DP표만 생각해도 된다. 

소스 코드

더보기
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <queue>
#include <math.h>
#include <memory.h>
 
 
int readInt();
 
 
int N, K;
int X[3001], Y[3001];
 
void GatherInput() {
    N = readInt();
    K = readInt();
    for (int i = 1; i <= N; i++) X[i] = readInt();
    for (int i = 1; i <= N; i++) Y[i] = readInt();
}
 
// DP[i][j] = X[1..i], Y[1..j]가 남았을 때 이길 수 있는지; 1=승, 0=패
int DP[3001][3001];
 
// SummableX[i] = X[j..i] 합이 k 이하인 j값 중 가장 작은 것
int SummableX[3001], SummableY[3001];
 
// DP_PsumX[i+1][j+1] = DP[0][j] + DP[1][j] + ... + DP[i][j].
// DP_PsumY[i+1][j+1] = DP[i][0] + DP[i][1] + ... + DP[i][j].
int DP_PsumX[3002][3002], DP_PsumY[3002][3002];
 
void Solve() {
    auto compute_summables = [](int* in, int* out, int Count) {
        /* two-pointer algorithm */
        out[1= 1;
        int sum = in[1], p = 1;
        for (int i = 2; i <= N; i++) {
            sum += in[i];
            while (sum > K) sum -= in[p++];
            out[i] = p;
        }
    };
    compute_summables(X, SummableX, N);
    compute_summables(Y, SummableY, N);
 
    /* actual DP */
    // DP[i][j] = (k-j, i-k들 중, 가능한 것이 있을 때,
    //             그 k중 이길 수 있는 방법이 하나라도 있으면 1 없으면 0)
 
    DP[0][0= 1;
    memset(DP_PsumX, 0sizeof(DP_PsumX));
    memset(DP_PsumY, 0sizeof(DP_PsumY));
    DP_PsumX[1][1= DP_PsumY[1][1= DP[0][0];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            if (i == 0 && j == 0continue;
 
            int lo;
            bool Winnable = false;
 
            /* picking from deck X */
            if (i > 0) {
                lo = SummableX[i];
                if (DP_PsumX[i][j + 1- DP_PsumX[lo - 1][j + 1< (i - lo + 1)) {
                    /* DP[lo - 1][j] + DP[lo][j] + ... + DP[i - 1][j] 중 0이 있음 */
                    Winnable = true;
                }
            }
 
            /* picking from deck Y */
            if (j > 0) {
                lo = SummableY[j];
                if (DP_PsumY[i + 1][j] - DP_PsumY[i + 1][lo - 1< (j - lo + 1)) {
                    /* DP[i][lo - 1] + DP[i][lo] + ... + DP[i][j - 1] 중 0이 있음 */
                    Winnable = true;
                }
            }
 
            /* save and cleanup */
            DP[i][j] = Winnable ? 1 : 0;
            DP_PsumX[i + 1][j + 1= DP_PsumX[i][j + 1+ DP[i][j];
            DP_PsumY[i + 1][j + 1= DP_PsumY[i + 1][j] + DP[i][j];
        }
    }
 
    int WinnableStates = 0;
    for (int i = 0; i <= N; i++) WinnableStates += DP_PsumY[i + 1][N + 1];
    int LosingStates = (N + 1* (N + 1- WinnableStates;
 
    printf("%d %d\n", WinnableStates, LosingStates);
}
 
 
 
int main() {
    int T = readInt();
    setbuf(stdout, NULL);
 
    for (int test_case = 1; test_case <= T; test_case++) {
        GatherInput();
        printf("Case #%d\n", test_case);
        Solve();
    }
    return 0;
}
 
int readInt() {
    int p;
    scanf("%d"&p);
    return p;
}
 
cs

문제 3. 사다리 게임

설명

\(N\)개의 세로선과 \(K\)개의 가로선으로 구성된 사다리가 있다. 세로선 중 일부를 없앨 수 있지만, 추가하거나 변형하는 것은 불가능하다고 하자.

 

이제 \(M\)개의 쿼리가 주어진다. 각 쿼리는 \((i, j)\) 형태로, 위에서 \(i\)에서 시작하여 아래에서 \(j\)로 끝나기 위해 제거해야 하는 최소 가로선 수를 계산해야 한다. 만약 어떤 방법도 불가능하면 -1로 계산한다. 모든 쿼리에 대해 최소 가로선 수를 합친 값을 출력하라.

 

제한조건: \(2 \le N \le 1,500\), \(1 \le K \le 2,000\), \(1 \le M \le 100,000\)

실행조건: 70개 이하 테스트 케이스에 대한 실행시간 총합 3초 이내

풀이

DP 문제이다. \(N\)과 \(K\)가 작으므로, 모든 \((i,j)\) 조합을 미리 계산해놓고 쿼리를 처리해도 된다. 따라서 DP[i][j]를 계산하자.

 

초기조건은 가로선이 없는 맨 위에서 출발한 것으로 하여, DP[i][j]를 모두 INF로 채우되 i와 j가 같을때만 0으로 한다. (가로선이 없으므로 다른 곳으로 아예 갈 수 없는 상황이다.)

 

상태전이는 사다리 위에서 아래로 내려오면서 가로선을 하나씩 처리하면 된다. 이전 단계에서 작성한 DP표는 현재 단계 가로선 바로 위 가로선까지를 고려했을 때의 최적값을 담고 있다. 이를 DP_Prev[i][j]라 하고, 현재 단계에서 새로 작성하는 DP표를 DP[i][j]라고 하자.

 

현재 단계 가로선을 \(a - b\)라고 하면,

  • \((i,j)\) 중 \(j\)가 a나 b 중 어느 것과도 일치하지 않는 것은 영향받지 않으므로 그대로 둔다.
    • 즉, DP[i][j] = DP_Prev[i][j].
  • \((i,j)\) 중 \(j\)가 a나 b 중 어느 하나와 일치한다면
    • \(a - b\)를 제거하는 경우: (이전 DP값) + 1, 즉 DP_Prev[i][j] + 1이다.
    • \(a - b\)를 유지하는 경우: 지금 j로 간다면 이전에 i였어야 하고, 반대도 같다. 따라서 DP_Prev[i][a+b-j]이다.
    • 즉, DP[i][j] = min(DP_Prev[i][j] + 1, DP_Prev[i][a+b-j]).

 

이렇게 하면 매 상태전이가 \(O(N)\)이므로 전체 가로선을 처리하는 데는 \(O(NK)\)번의 갱신으로 충분하다. (* 구현 노트 1번 참조.) 총 시간복잡도는 \(O(NK + M)\).

 

* \((i, j)\) 중 \(i\)는 맨 위쪽의 출발점을 나타내므로, 아래쪽에 새로 나타난 가로선과는 멀리 떨어져 있다. 따라서 상태전이와 관련이 없다.

구현 노트

  1. 상태전이 단계에서, 새로운 DP표를 계산하기 위해 이전 DP표(DP_Prev)를 백업하고 새롭게 계산하는 경우, 메모리 복사로 인해 시간복잡도가 \(O(N^2K)\)가 되어 시간초과가 발생하였다. 따라서, 새롭게 갱신할 목록을 std::vector에 저장하고, 모든 것을 계산한 다음, DP표에 반영하는 2단계 방식을 쓰면 시간초과를 피할 수 있었다. 이렇게 하면, 각 세로선마다 새롭게 갱신하는 DP표의 항목수가 \(O(N)\)개이기 때문에, 전체 시간복잡도가 \(O(NK)\)로 줄어든다.
  2. DP 중에는 불가능한 \((i,j)\) 조합을 아주 큰 수로 표기하고, DP가 끝난 다음에 -1로 바꾸는 쪽이 편했다. DP 중간에 min을 사용하기 때문이다.

* 같진 않지만 비슷한 문제로 '잭과 콩나물'이 있다. 문제해결을 위한 창의적 알고리즘(고급)에 해당 문제와 해설이 있다.

소스 코드

더보기
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <functional>
#include <queue>
#include <math.h>
#include <memory.h>
 
 
int readInt();
 
 
int N, K, M;
int L[2001], R[2001];
int QTop[100000], QBottom[100000];
 
 
void GatherInput() {
    N = readInt();
    K = readInt();
    M = readInt();
 
    for (int i = 1; i <= K; i++) L[i] = readInt(), R[i] = readInt();
    for (int i = 0; i < M; i++) QTop[i] = readInt(), QBottom[i] = readInt();
}
 
int DP[1501][1501];
static const int INF = 2001;
 
struct Update {
    int start, end, val;
    Update(int s, int e, int v) : start(s), end(e), val(v) {}
};
 
void Solve() {
    /* DP table: init */
    memset(DP, 0x3fsizeof(DP));
    for (int i = 1; i <= N; i++) DP[i][i] = 0;
 
    /* DP table: recurrence */
    for (int h = 1; h <= K; h++) {
        int i = L[h], j = R[h]; // i<j 보장됨.
        std::vector<Update> upd;
 
        /* case 1: i 또는 j에서 끝나는 경우 */
        auto update = [&](int start, int end) {
            int val = INF;
            val = std::min(val, DP[start][i + j - end]); // keep
            val = std::min(val, DP[start][end+ 1); // remove
            upd.push_back(Update(start, end, val));
        };
        for (int k = 1; k <= N; k++) { /* k->i and k->j */
            update(k, i);
            update(k, j);
        }
 
        /* case 2: i 또는 j에서 끝나지 않는 경우: 할 일 없음.
                   (없애지 않는 게 최선) */
 
        /* apply updates */
        for (auto& u : upd) {
            DP[u.start][u.end= u.val;
        }
    }
 
    /* compute answer */
    int sum = 0;
    for (int i = 0; i < M; i++) {
        int opt = DP[QTop[i]][QBottom[i]];
        if (opt >= INF) opt = -1;
        sum += opt;
    }
    printf("%d\n", sum);
}
 
 
 
int main() {
    int T = readInt();
    setbuf(stdout, NULL);
 
    for (int test_case = 1; test_case <= T; test_case++) {
        GatherInput();
        printf("Case #%d\n", test_case);
        Solve();
    }
    return 0;
}
 
int readInt() {
    int p;
    scanf("%d"&p);
    return p;
}
cs

문제 4. 범위 안의 숫자

설명

0-9의 숫자 \(n\)개로 이루어진 문자열 \(t\)가 주어진다. \(t\)에서 길이 \(k\)인 부분문자열을 모두 취하여 숫자를 만든다. 중복되는 숫자가 있다면 따로 센다. (즉, 중복을 포함하여 \(n-k+1\)개의 숫자가 나온다.)

 

이 숫자들을 수직선 위에 배열하자. 이제 길이 \(m\)인 구간 \([a, a+m]\) (\(m\)은 고정)에 대해 \(a\)를 변화시켜가며, \([a, a+m]\)이 가장 많은 숫자를 포함하는 위치를 찾는다. 이를 '(\(t\)의) 구간 안의 수의 (개수의) 최댓값'이라고 하자.

 

이를테면, \(t = 0010222\), \(k = 3\), \(m = 100\)의 경우 001, 010, 102, 022, 222가 나온다. 이를 오름차순으로 배열하면 001, 010, 022, 102, 222가 된다. 길이 \(m = 100\)인 구간을 움직이면서 보면, 같이 포함되는 것은 {}, {001}, {001, 010}, {001, 010, 022}, {010, 022}, {010, 022, 102}, {022, 102}, {102}, {}, {222}, {} 순서로 나타난다. 따라서 '(0010222의) 구간 안의 수의 (개수의) 최댓값'은 {001, 010, 022} 혹은 {010, 022, 102}에서 나타나는 3개가 최대이다.

 

여기까지만 풀면 너무 쉬우니까, \(t\)의 임의의 위치 하나를 골라 그 자리의 숫자를 1로 바꿀 수 있다고 추가로 가정한다. 즉, 위의 예시에서는 \(t = 1010222, 0110222, 0010222, 0011222, 0010122, 0010212, 0010221\)에 대한 경우를 추가로 풀어야 한다. 1로 바꾼 경우와 원래 경우까지 총 \(n+1\)개의 문자열에 대해 '(해당 문자열의) 구간 안의 수의 (개수의) 최댓값' 중 최댓값을 '(전체 문자열의) 구간 안의 수의 (개수의) 최댓값'이라고 할 때, 이를 구하여라.

 

제한조건: \(1 \le n \le 50,000\), \(1 \le k \le \min\lbrace9,n\rbrace\), \(0 \le m \le 1,000,000,000\)

실행조건: 40개 이하 테스트 케이스에 대한 실행시간 총합 10초 이내

풀이

가능한 숫자들의 범위가 매우 크므로, 기하 문제에서 인덱스(좌표) 압축을 하듯이 여기서도 인덱스 압축을 우선 적용해보자. 범위를 따져보면, 길이가 \(n\)인 문자열에서 \(k \le 9\)개의 부분문자열*을 숫자로 취하므로, \(O(n)\)개의 절단이 가능하다. 여기에 각 부분문자열을 1) 그대로 유지하거나 2) 한 자리만을 골라 1로 바꾸므로, 자리마다 \(O(k)\)개의 가짓수가 생긴다. 총 \(O(nk)\)의 가짓수인데 제한조건상 500,000가지 이하이다. 이 가짓수를 \(P\)라 하자. 가능한 모든 숫자를 모아 오름차순 정렬한 뒤 (서로 다른 숫자들에) 순서대로 1, 2, ..., \(P\)의 인덱스를 준다. i번째 숫자를 배열 A[i]에 저장한다고 하자. \((1 \le i \le P)\) 정렬이 들어가므로 시간복잡도는 \(O(P \lg P)\).

 

* \(k \le 9\)이므로, 각 숫자를 int형으로 표현할 수 있다.

 

그런 다음, 주어진 문자열 \(t\)에서 각 A[i]의 등장횟수를 기록하면 길이 \(P\)의 배열이 나올 것이다. 이를 ACnt[i]라고 하자. 여기서 투 포인터를 써서 이동하며 길이가 \(m\)이하인 모든 구간을 고려하면, 주어진 문자열에 대한 '구간 안의 수의 (개수의) 최댓값'이 나온다. 시간은 \(O(nk)\).

 

여기까지만 풀면 너무 쉬우니까 이제 문자열 \(t\)에서 각 위치를 1로 바꿔가며 이 작업을 반복하면 된다. 위치가 \(O(n)\)개이므로 총 시간은 \(O(n^2k)\)가 든다. 따라서 부분문제 1 \((n \le 1,000)\)은 해결된다.

 

하지만 전체 문제는 추가 최적화가 필요하다. 어떤 redundancy를 공략해야 할까. 잘 생각해보면 원래 문자열과 바뀐 문자열이 크게 차이나지 않음을 알 수 있다. 즉, 조금만 바뀌었을 때 그 조금이 우리가 하는 일에서도 조금으로 이어지면 될 것이다.

 

관찰 1. 문자열 \(t\)에서 어떤 위치를 1로 바꿀 때 영향을 받는 A[i]는 기껏해야 \(2k\)개이다. 사라지는 것이 최대 \(k\)개, 생기는 것이 최대 \(k\)개다.

 

이것이 무엇을 의미할까? 어떤 위치를 1로 바꿀 때 갱신해야 하는 ACnt[i] 수는 기껏해야 \(2k\)개이므로, 한 가지를 갱신할 때 전체 값('구간 안의 수의 (개수의) 최댓값')을 빠르게 갱신해줄 수 있는 자료구조를 사용한다면 전체 문제를 풀 수 있다는 뜻이다.

 

언뜻 보기에 세그먼트 트리를 사용하면 될 것 같다. 하지만 우리 상황이 조금 복잡하다. 단순히 ACnt[i]에 대한 최댓값이 필요한 것이 아니라, 길이 \(m\)짜리 폐구간 M 내에 포함된 각 A[i]에 대해 ACnt[i]를 모두 더한 값이 최대가 되는 구간 M을 찾고, 거기서 최댓값을 얻어야 한다. 따라서 세그먼트 트리 계열 자료구조를 사용하기에 적합하도록, 상황을 만들어보자.

 

한 가지를 관찰해보면, 길이 \(m\)짜리 구간을 전부 고려할 필요가 없다. 구간 내에 포함된 A[i]가 서로 같기만 하면 '구간 안의 수의 (개수의) 최댓값'이 서로 같으므로, 구간을 전부 다 오른쪽으로 밀어버리자! 그러면 왼쪽 끝점이 A[i] 중 하나가 된다. 따라서, 우리가 구간을 고려할 때 A[i]가 왼쪽 끝점인 구간만 고려해도 충분하다. 그러한 구간은 A[i]의 개수만큼, 즉 \(P\)개만큼 있다. A[i]를 왼쪽 끝점으로 하는 길이 \(m\)짜리 구간을 \(J_i\)라고 하자.

 

그러면 A[i]의 ACnt[i]가 변할 때 영향 받는 구간은 어디 어디일까? 잘 생각해보면, 어떤 j = j(i)에 대하여 \(J_j\)부터 \(J_i\)까지이다(\(1 \le j \le i\), 경계포함). 각 i에 대하여 j = j(i)를 구하기 위해서는 투 포인터를 사용하면 \(O(P)\)에 해결 가능하다. 이를 구하여 저장해놓자.

 

이처럼, 봐야 하는 구간을 A[i]를 기준으로 \(P\)개로 축소하고 나면, 어떤 A[i]의 개수가 변할 때 영향을 받는 구간의 인덱스도 연속적인 하나의 구간으로 나타난다. (물론 축소하기 전에도 연속이지만, 축소하고 나서도 연속이라는 점이 중요하다. 이는 A[i]를 앞서 정렬해놓았기 때문에 성립한다.)

 

그러면 이제 세그먼트 트리를 적용할 수 있다. (단, 점갱신(point update)이 아닌 구간갱신(range update)이므로 지연전파(lazy propagation) 기법을 필수적용해야 한다.) 먼저 리프 노드 수가 \(P\)인 세그먼트 트리를 구축하자. 어떤 A[i]의 개수가 d만큼 변할 때, 세그먼트 트리의 노드 중 j(i) ~ i 구간을 d만큼 더해 갱신하면 된다. (세그먼트 트리의 추적대상은, 당연히, 최댓값으로 한다.)

 

정리하면, 전체 고려할 i의 가짓수가 \(n\)개, 각 i에 대해 갱신할 횟수가 \(O(k)\)개, 쿼리는 1회, 되돌려놓을 때 갱신할 횟수도 \(O(k)\)이므로, 갱신횟수는 총 \(O(nk)\)이다. 1회 갱신의 시간복잡도는 \(O(\lg P)\)이므로, 갱신과 쿼리의 총 시간복잡도는 \(O(nk \lg P)\)이다. \(nk \le 450,000\), \(P \le 500,000\)이므로, 충분히 시간 내에 해결 가능하다. 전체 시간복잡도는 \(O(nk \lg P)\)에 더하여 가장 처음에 들어가는 \(O(P \lg P)\)를 고려해야 하지만, 어차피 비슷하다.

구현 노트

  1. 문제에 0에 대한 언급이 있지만, 0을 특별하게 취급할 필요가 전혀 없었다.

소스 코드

길어서 별도의 게시물로 분리 (https://paido.tistory.com/22 참조)

문제 5. 우범 지역

설명

철수네 집은 q점에 있고, 주변에 \(N\)개의 위치 \(a_1, ..., a_N\)이 있다. 각 위치 \(a_i\)에는 범죄가 일어날 확률 \(p_i\) \((0 < p_i \le 1)\)가 주어진다. (어느 \(i \neq j\)에 대해서도 \(q\), \(a_i\), \(a_j\)는 한 직선 위에 있지 않다.)

 

범죄가 실제로 발생한 지역들을 모아 Convex Hull을 잡았을 때, 이 Convex Hull이 q점을 포함할 확률을 구하여라.

 

제한조건: \(3 \le N \le 100,000\), 모든 좌표값은 1 이상 1,000,000,000 이하, 모든 \(p_i\)는 소수점 2자리 실수

실행조건: 70개 이하 테스트 케이스에 대한 실행시간 총합 2초 이내

풀이

각각의 점 \(a_i\)는 \(p_i\)의 확률로 선택된다. 이는 점의 집합을 형성한다. 모든 가능성에 대해 각 집합이 우범지역인지 판정할 수 있다면, 적어도 개념적으로는 문제가 풀린다.

따라서 확률은 잊고, 일단 점의 집합이 주어졌다고 생각해보자. 문제조건상 q를 중심으로 모든 점이 서로 다른 방위에 있다.

 

어떤 점의 집합 \(S = \lbrace a_i, a_j, ...\rbrace\)이 선택되었을 때 그것의 Convex Hull이 q를 포함할지 여부는 \(S\)의 '각도 스팬'이 180도를 넘는지와 동치이다. (여기서 '각도 스팬'이란 \(S\)의 Convex Hull에 의해 점유되는 전체 각도를 말한다. 즉, \(S\)의 Convex Hull의 모든 점과 q를 연결하였을 때 q에 나타나는 각도를 말한다. 다르게 표현하면, q를 중심으로 하는 반지름 1인 원 위로 \(S\)의 Convex Hull을 투영했을 때 나타나는 원호의 길이를 말한다. 원호는 절대로 끊어져있지 않은데, 이는 원래 도형인 Convex Hull이 끊어져있지 않기 때문이다. 다른 방법으로 생각하면, 원호가 끊어져있다면, 그 두 끝점으로 투영된 원래의 두 점이 있을텐데, 그들을 이은 선분은 Convex Hull 내부에 포함돼야 하고, 그 선분의 투영은 원호가 끊어진 부분을 결찰해야 하므로, 원호가 끊어져 있었다는 가정에 모순이다.)

 

즉, \(S\)의 각도 스팬이 180도보다 작으면 q를 포함하지 않고, 180도보다 크면 q를 포함한다. 정확히 180도는 될 수 없다(q를 중심으로 모든 점이 서로 다른 방위에 있기 때문).

 

각도 스팬이 180도보다 작은 어떤 Convex Hull A를 생각하면, (반시계 방향으로 봤을 때) 가장 먼저 나오는 점이 있을 것이다. 이 점(\(a_i\)라 하자)은 정확히 하나만 있으므로, 그러한 각각의 Convex Hull은 \(a_i\)에 따라 분류할 수 있다.

  따라서, 임의의 한 점 \(a_i\)를 잡고, 그 점에서 반시계 방향으로 0도 이상 180도 미만인 영역에 포함되는 점들을 생각하자. 이를 집합 \(P\)라 하고, 남은 점들을 집합 \(Q\)라 하면, \(Q\)에 포함된 점들은 반드시 제외해야 하고, \(P\)의 점들은 포함 여부가 상관이 없으며, \(a_i\)는 반드시 포함해야 한다. 따라서,

  • \(a_i\)가 선택될 확률
  • \(Q\)의 각 점 \(a_j\)에 대해, \(a_j\)가 선택되지 않을 확률 

을 모두 곱하면 그것이 바로 (각도 스팬이 180도보다 작은 Convex Hull 중 (반시계 방향으로 봤을 때) 가장 먼저 나오는 점이 \(a_i\)인 Convex Hull이 나올 전체 확률)이다. 이를 모든 \(a_i\)에 대해 더하면 (최소한 한 점을 포함하는 비우범지역이 도출될 전체 확률)이 얻어진다. 여기에 더하여, 어떤 점도 선택되지 않는 경우를 고려하면 (비우범지역이 도출될 전체 확률)이 얻어진다. (우범지역이 도출될 전체 확률)은 1에서 이를 빼면 된다.

구현

위의 \(a_i\)에 대한 계산을 naive하게 하면 한 번 할 때마다 \(O(N)\)이 든다. 전체는 \(O(N^2)\). 따라서 부분문제 1만 해결되므로 추가 최적화가 필요하다. 크게 두 가지가 있다.

  1. \(a_i\)를 방위 순서대로 고려한다면, 바로 앞의 점이 어디까지 뻗치는지를 알고 있으므로, 거기서부터 더 가는 것만 고려하면 되지 그 이전을 굳이 고려할 필요가 없다. 즉, 투 포인터의 각도 버전을 적용할 수 있다. 그러면 각도 스팬이 180도보다 작은 구간을 찾는 일은 amortized O(1)이다.
  2. 집합 \(Q\)의 각 점이 선택되지 않을 확률의 곱을 계산할 때, 이 곱은 연속된 구간의 '곱'이므로 Prefix Sum을 적용하기 위해 Logarithm을 취하여 곱을 '합'으로 바꾼다. 계산이 끝난 다음 Exponential을 취하여 원래의 확률로 되돌린다. (이번에는 노파심에 long double을 이용했지만 굳이 그럴 필요는 없을 것 같기도 하다.)

구현 노트

  1. q를 중심으로 방위에 따라 점들을 정렬한다. (이때 각은 주기적으로 반복되므로 임의로 기준을 정해 끊어야 한다. 한 가지 방법은, 어느 사분면 혹은 축에 속하는지에 따라 일단 분리를 한 후, 그 속하는 곳이 같을 때 외적(CCW)을 이용해 각을 비교하는 것이다.)
  2. 문제 조건상 선택될 확률은 0이 될 수 없지만 선택되지 않을 확률은 0이 될 수 있다. 따라서, 확률의 Logarithm을 취할 때 그것이 0이라면 취하지 않고 건너뛰어야 한다. 대신 별도의 배열에 그것을 건너뛰었다고 표시한다. 이 건너뜀 배열 역시 확률의 Logarithm과 마찬가지로 Prefix Sum을 해 놓으면 나중에 구간 쿼리를 해서 불가능한 것이 있는지 O(1)에 확인할 수 있다.

소스 코드

길어서 별도의 게시물로 분리 (https://paido.tistory.com/23 참조)