SCPC 2020 Round 1 문제 풀이 및 후기

작성일 | In |

SCPC 삼성 프로그래밍 경진대회

result

결과

  • 다이어트: 100/100점
  • 카드 게임: 150/150점
  • 사다리 게임: 150/150점
  • 범위 안의 숫자: 200/200점
  • 우범 지역: 0/200점

먼저 쓰는 느낀 점

무난하게 Round 2로 갈것같다. All solve하고 싶었지만 마지막 문제 풀이를 전혀 생각 못했다. 5번은 기하 문제였는데 기하 연습좀 해야겠다. 만점이 45명 정도인데 scpc수상하려면 5번 정도 수준의 문제를 대회시간에 풀 실력을 키워야겠다. 나름 할만큼 했는데 주변에 올솔이 너무 많다 ㅠ

디스크립션이 살짝 이상한 부분이 있었다.

cgiosy, 파이도, rkm0959 님의 후기를 참고하여 작성했습니다.

다이어트

길이 $N$인 배열 $A$와 $B$에서 각각 $K$개의 수를 골라 그 합의 최댓값을 최소화하여라. $A$와 $B$의 순서는 마음대로 바꿀 수 있고 한 번 쓴 수는 다시 쓸 수 없다.

  • 제한조건
\[1 ≤ N ≤ 200,000 1 ≤ K ≤ N, 1 ≤ A[i] ≤ 10^9\]

다이어트-풀이

  • 그리디
  • 정렬
  1. $A$와 $B$에서 가장 작은 $K$개의 수만 사용해야 한다.
  2. $A$와 $B$를 오름차순 정렬했을 때 $A[1]$은 $B[K]$와 매칭하면 답을 구할 수 있다.
    • 증명: 만약 그렇지 않다면 $A[1]$이 $B[i] (i \ne K)$ 와 매칭되고 $A[j] (j \ne 1)$ 가 $B[K]$와 매칭되는데 $A[j] + B[K] ≤ max(A[1] + B[K], A[i] + B[j])$ 이기 때문이다.
  3. $A[2..K]$ 와 $B[1..K-1]$ 에 대해서도 2번을 동일하게 적용하면 된다.

시간 복잡도는 $K$개를 정렬하는데 드는 속도인 $O(NlogK)$이다.

다이어트-여담

가장 쉬운 문제. 보자마자 풀었다. 부분 점수는 모든 경우를 다 해보면 얻을 수 있었던걸로 기억한다.

다이어트-코드

실제 제출한 코드와는 다르다

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
#include <bits/stdc++.h>
using namespace std;
const int MAX = 20000;

int A[MAX], B[MAX];
void solve() {
    int N, K; scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++)
        scanf("%d", A+i);
    for (int i = 0; i < N; i++)
        scanf("%d", B+i]);
    partial_sort(A, A+K, A+N);
    partial_sort(B, B+K, B+N);
    int ans = 0;
    for (int i = 0; i < K; i++)
        ans = max(ans, A[i]+B[K-i-1]);
    printf("%d\n", ans);
}

int main() {
    // setbuf(stdout, NULL);
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        printf("Case #%d\n",i);
        solve();
    }
}

카드 게임

두 사람이 길이 $N$의 배열 $X$와 $Y$로 게임을 한다. 둘이 번갈아 가며 턴을 진행하며, 각 턴에선 원하는 배열 하나에서 맨 뒤의 수들을 여러 개 지울 수 있다. $X$와 $Y$의 수는 모두 $K$ 이하고 지우는 수들의 합이 $K$ 이하여야 한다. 둘은 최선의 전략으로 게임을 하며, 자신의 턴에서 남아있는 수가 없는 사람이 이긴다.

X와 Y에 남아있는 수의 개수를 $i$, $j$개라고 할 때, 해당 상태에서 선공이 이길지 후공이 이길지는 정해져 있다. 모든 가능한 상태 $(N+1)^2$ 개 중 $(i, j)$에서 선공이 이기는 상태의 수와 후공이 이기는 상태의 수를 구하시오. 단, 상태 $(0, 0)$은 선공이 이긴 상태로 본다.

  • 제한 조건
\[1 ≤ N, K ≤ 3000\\1 ≤ A[i] ≤ K\]

카드 게임-풀이

  • DP

부분 점수

  1. $(i, j)$ 상태 값이 $WIN$인지 $LOSE$인지 알려면 상대방에게 $(i’, j’)$ 로 바뀌어 넘겨주었을 때의 값들을 이용해 알 수 있다.
  2. 만약 $(i’, j’) = LOSE$로 변환할 수 있다면 $(i, j) = WIN$, 없다면 $(i, j) = LOSE$ 이다.

이때 채워야할 값은 $(N+1)^2$ 이고 각 칸 마다 최대 $2N$개의 값을 확인해야하기 때문에 시간 복잡도는 $O(N^3)$이다.

만점

  1. 한번에 하나의 배열만 건드릴 수 있으므로 $(i’, j’)$ 는 $(i, j’)$ 이거나, $(i’, j)$이다. 이때 $i’$의 최솟값을 $a$, $j’$의 최솟값을 $b$라고 할수 있다.
  2. 그렇다면 $(i, [b..j-1])$, $([a..i-1], j)$에 $LOSE$가 있는지 빠르게 판별하면 $(i, j)$의 값을 알 수 있다.
  3. 연결된 구간이므로 prefix sum을 통해 $O(1)$ 만에 구할 수 있다.

시간 복잡도는 $O(N^2)$이다.

카드 게임-여담

친구들을 보니 Grundy 게임으로 많이 접근을 해서 시간초과가 난것 같다.

카드 게임-코드

실제 제출한 코드와는 다르다

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
#include <bits/stdc++.h>
using namespace std;
int X[3001], Y[3001], N, K;
int xl[3001], yl[3001];
int xpsum[3001][3001], ypsum[3001][3001];

int getx(int i, int j) {
    if (i < 0) return 0;
    return xpsum[i][j];
}
int gety(int i, int j) {
    if (j < 0) return 0;
    return ypsum[i][j];
}

int go(int i, int j) {
    if (i == 0 && j == 0) return 1;
    if (gety(i, j-1) - gety(i, yl[j]-1) != j-yl[j])
        return 1;
    if (getx(i-1, j) - getx(xl[i]-1, j) != i-xl[i])
        return 1;
    return 0;
}

void solve() {
    int A = 0, B = 0;
    scanf("%d %d", &N, &K);
    int lb = 1, sum = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &X[i]);
        sum += X[i];
        while (sum > K) {
            sum -= X[lb];
            lb++;
        }
        xl[i] = lb - 1;
    }
    lb = 1, sum = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &Y[i]);
        sum += Y[i];
        while (sum > K) {
            sum -= Y[lb];
            lb++;
        }
        yl[i] = lb - 1;
    }

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            int ret = go(i, j);
            xpsum[i][j] = ypsum[i][j] = ret;
            if (ret == 1) A++;
            else B++;
            if (i) xpsum[i][j] += xpsum[i-1][j];
            if (j) ypsum[i][j] += ypsum[i][j-1];
        }
    }
    printf("%d %d\n", A, B);
}

int main() {
    // setbuf(stdout, NULL);
    int T; scanf("%d", & T);
    for (int i = 1; i <= T; i++) {
        printf("Case #%d\n",i);
        solve();
    }
}

사다리 게임

$N$개의 세로선이 있고 $M$개의 가로선이 있다. 가로선은 $(a, b)$ 순서쌍으로 이루어지며, 세로선 $a$와 세로선 $b$를 양방향으로 연결한다. $i$번째 세로선에서 모든 가로선을 타며 내려가면 $j$번째 세로선에 도착하게 되는데, 가로선을 최소한으로 지워 원하는 세로선으로 도착하도록 만드려고 한다.

즉, 사다리가 주어지면 $Q$개의 쿼리에 대해 $i$번째 세로선에서 시작해 $j$번째 세로선에 도착하도록 만들 때 최소한으로 지워야 하는 가로선의 개수의 합을 출력해야 한다. 만약 $i$에서 $j$로 갈 수 없다면 $-1$을 더한다.

  • 제한 조건
\[2 ≤ N ≤ 1500\\1 ≤ M ≤ 2000\\1 ≤ Q ≤ 10^5\\1 ≤ i < j ≤ N\]

사다리 게임-풀이

  • DP
  • 최단 경로
  • 0-1 BFS

여러가지 풀이가 있는 것으로 알고 있다. 나는 DP로 풀었다.

  1. $i$ 에서 $j$로 가기 위한 최소 제거 횟수를 $dp[i][j]$라 하자. dp 테이블의 초기값은 $dp[i][i] = 0$이고 $dp[i][j]=\infty (j \ne i)$

  2. $(u, v)$ 간선을 만나면 값을 $1$ 올리고 그대로 있거나, 값을 그대로 하고 바꾸는 선택이 가능하다. 최솟값을 계속 저장한다. 두 값을 동시 업데이트하는거에 주의를 해야한다.

\[dp[i][u] = min(dp[i][u]+1, dp[i][v])\\dp[i][v] = min(dp[i][v]+1, dp[i][u])\]

시간 복잡도는 $O(N^2 + NM + Q)$ 이다.

사다리 게임-여담

$-1$을 더하라는건 정말 :thinking_face: 이다.

사다리 게임-코드

실제 제출한 코드와는 다르다

구현에서는 업데이트가 필요한 것만 관리하기 위해서 큐를 사용했는데 그냥 $2N$개를 봐도 무방하다.

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
#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;

int N, K;
queue<int> q[1500];
int ans[1500][1500];
void solve() {
    int m;
    scanf("%d %d %d", &N, &K, &m);
    memset(ans, -1, sizeof(ans));
    for (int i = 0; i < N; i++) {
        q[i] = queue<int>();
        q[i].push(i);
        ans[i][i] = 0;
    }
    while (K--) {
        int a = scanf("%d", &a);
        int b = scanf("%d", &b);
        --a; --b;
        vector<int> A(N, INF), B(N, INF);
        while (!q[a].empty()) {
            int now = q[a].front(); q[a].pop();
            A[now] = ans[now][a] + 1;
            B[now] = ans[now][a];
        }
        while (!q[b].empty()) {
            int now = q[b].front(); q[b].pop();
            B[now] = min(B[now], ans[now][b] + 1);
            A[now] = min(A[now], ans[now][b]);
        }
        for (int i = 0; i < N; i++) {
            if (A[i] != INF) {
                q[a].push(i);
                ans[i][a] = A[i];
            }
            if (B[i] != INF) {
                q[b].push(i);
                ans[i][b] = B[i];
            }
        }
    }

    int ret = 0;
    while (m--) {
        int x, y; scanf("%d %d",&x, &y);
        ret += ans[x-1][y-1];
    }
    printf("%d\n", ret);
}

int main() {
    // setbuf(stdout, NULL);
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        printf("Case #%d\n",i);
        solve();
    }
}

범위 안의 숫자

숫자로 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$에서 임의의 숫자를 골라 1로 바꾸고, 연속한 $K$개의 숫자로 이루어진 수를 모두 나열했을 때 적절한 수 $a$를 골라 $[a, a + M]$에 있는 수의 개수를 최대화하여라.

  • 제한 조건
\[1 ≤ N ≤ 50000\\1 ≤ K ≤ min(9, N)\]

범위 안의 숫자-풀이

  • 세그먼트 트리
  • 좌표 압축
  1. $K$값이 작은 것에 주목한다. 총 나올 수 있는 길이 $K$의 수는 $N(K+1)$개 보다 작다. 이를 모두 구해 $V$에 저장한다.
  2. $V$를 정렬하고 좌표 압축을 한다.
  3. $V$에 있는 각 원소 $a$에 대해서 $[a, a+M]$에 포함되는 $V$의 최대 인덱스 번호를 저장한다.
  4. range update를 지원하는 maximum segment tree를 만든 다음, 아무것도 바꾸지 않은 $S$에 대해서 $K$개의 연속된 숫자로 이루어진 수를 모두 업데이트를 한다. 이 때 업데이트를 할때 그 수의 인덱스 번호부터 3에서 구한 최대 인덱스 번호까지 구간 업데이트를 한다. 이를 통해 각 node의 말단에는 그 수를 마지막으로 하는 구간에 해당하는 개수를 알 수 있다.
  5. $S$의 $i$번째 숫자를 $1$로 바꾸었을때 바귀는 값을 빼고 넣고하는 과정을 반복하며 최대값을 갱신한다.

시간 복잡도는 $O(NKlog(NK))$이다.

제한시간이 10초지만 상수가 크고 테스트케이스가 있기 때문에 최적화를 조금 해야 할 수 있다.

범위안의 숫자-여담

구현을 정말 애먹었다.무려 7번 틀렸다. 인덱스 실수 하고 시간초과 나고, 대회 때는 나만 그런줄 알았는데 끝나고 보니 다들 그래서 조금 안심이다.

세그먼트트리를 안쓰고도 풀 수 있다는데 나중에 다시 봐야겠다.

범위안의 숫자-코드

공개하기 정말 부끄러운 코드인데(real_solve 등) 다시 짜기는 또 귀찮다.

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 50'000;

ll ten[10]={1};
char s[MAX+5];
int n, k, m, sz;
int ub[MAX*10+5];
int t[MAX*41], lazy[MAX*41];
vector<int> base, a[MAX+5], b[MAX+5];
vector<ll> nums;
unordered_map<int,int> hsh;

void push(int v) {
    t[v*2] += lazy[v];
    lazy[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r)
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}

void update(int l, int r, int addend) {
    update(1, 0, sz-1, l, r, addend);
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l <= tl && tr <= r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)),
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

int query() {
    return query(1, 0, sz-1, 0, sz-1);
}

void init() {
    base.clear();
    nums.clear();
    hsh = unordered_map<int,int>();
    memset(t, 0, sizeof(t));
    memset(lazy, 0, sizeof(lazy));

}

void get_number() {
    ll val = 0;
    for (int i = 0; i < k - 1; i++) {
        val = val * 10 + s[i] - '0';
    }
    for (int i = k - 1; i < n; i++) {
        val = val * 10 + s[i] - '0';
        val %= ten[k];
        nums.push_back(val);
        base.push_back(val);
        int x = val;
        for (int j = 0; j < k; j++) {
            int digit = (val % ten[j+1]) / ten[j];
            if (digit == 1) continue;
            b[i-j].push_back(val);
            val -= (digit - 1) * ten[j];
            nums.push_back(val);
            a[i-j].push_back(val);
            val += (digit - 1) * ten[j];
        }
    }

    sort(begin(nums), end(nums));
    nums.erase(unique(begin(nums), end(nums)), end(nums));

    sz = nums.size();
    for (int i = 0; i < sz; i++) {
        hsh[nums[i]] = i;
    }
    int idx = 0;
    for (int i = 0; i < sz; i++) {
        while (nums[i] - nums[idx] > m) {
            ub[idx] = i - 1;
            idx++;
        }
    }
    for (; idx < sz; idx++) {
        ub[idx] = sz - 1;
    }
}

void real_solve() {
    for (int i : base) {
        int idx = hsh[i];
        update(idx, ub[idx], 1);
    }
    int ans = query();
    for (int i = 0; i < n; i++) {
        for (int j : a[i]) {
            int idx = hsh[j];
            update(idx, ub[idx], 1);
        }
        for (int j : b[i]) {
            int idx = hsh[j];
            update(idx, ub[idx], -1);
        }
        ans = max(ans, query());
        for (int j : a[i]) {
            int idx = hsh[j];
            update(idx, ub[idx], -1);
        }
        for (int j : b[i]) {
            int idx = hsh[j];
            update(idx, ub[idx], 1);
        }
        a[i].clear();
        b[i].clear();
    }
    printf("%d\n", ans);
}

void solve() {
    scanf("%d %d %d %s", &n, &k, &m, s);
    init();
    get_number();
    real_solve();
}

int main() {
    // setbuf(stdout, NULL);
    for (int i = 1; i <= 10; i++)
        ten[i] = 10 * ten[i-1];
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        printf("Case #%d\n",i);
        solve();
    }
}

우범 지역

N개의 점 $(x_i, y_i)$들이 주어지는데, 각 점에는 선택될 확률 $p_i$이 있다. 선택된 점들의 컨벡스 헐에 점 $q$가 포함될 확률을 구하시오. 단, $q$와 임의의 서로 다른 두 점을 골랐을 때 직선 상에 놓여있지 않는다.

  • 제한 조건
\[1 ≤ N ≤ 100000\\1 ≤ x_i, y_i ≤ 10^9\\0 < p_i ≤ 1\]

우범 지역-풀이

풀이를 알려주신 @Miren0923님께 감사드립니다.

  • 기하
  • Sliding window
  1. 컨벡스 헐에 점이 있는 경우를 생각하는 것보다 컨벡스헐에 점이 없는 경우를 생각하는 것이 더 쉽다.
  2. “점 $q$가 컨벡스헐에 들어가지 않는다.”와 “점 $q$와 나머지 선택된 점을 가르는 직선이 있다”가 동치
  3. 점 $q$를 중심으로 나머지 점을 (각도를 기준으로) 원주에 올리면, 점이 하나도 없는 180도 길이의 구간이 있는 확률이 답
  4. 선택된 점이 없는 경우의 확률 + 선택된 점이 있는 경우의 확률을 더하면 된다.
    • 점이 없는 경우: 모든 점마다 선택되지 않을 경우 확률 곱
    • 점이 있는 경우: 모든 점마다 (자신이 선택될 확률) * (180도 이후에 점이 선택되지 않을 확률의 곱)
  5. (180도 이후에 점이 선택되지 않을 확률의 곱)을 구하려면 sliding window를 통해서 구할 수 있다.
    • 여기서 실수 오차가 나는걸 방지 하기 위해서(나눗셈 없이) sparse table을 사용하면 된다.
    • 그밖에도 세그먼트트리를 사용하거나 로그값을 이용해서 실수오차를 방지할 수 있다.

확률 자체는 빠르게 구하면 $O(N)$만에 구할 수도 있지만 결국 정렬을 해야해서 전체 시간 복잡도는 $O(NlogN)$이다.

우범 지역-여담

못 풀었다. 전혀 접근 자체를 하지 못했고 확률 문제다 보니 몬테 카를로로 비벼라도 볼까 했으나 여의치 않았다. 0번을 생각하면 2번까지 생각하고, 점이 있는 경우 처리하면서 재밌게 고민햇을텐데 0번을 생각하지 못했다.

브루트 포스로 $O(NlogN * 2^N)$ 에 짜는것 밖에 생각이 안났다. 저 2^N을 줄이기 위해서 생각을 많이 했다. 들로네 삼각분할을 쓰고 전처리? meet-in-the-middle? 스위핑? 전혀 아니었다.

우범 지역-코드

Juno의 코드를 변형했다.

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int MAX = 200000;
typedef long double ld;
struct point {
    ll x,y;ld p;
    point(ll x, ll y,ld p=0):x(x),y(y),p(p){}
    ll operator/(point b)const{return x*b.y-y*b.x;}
    inline int sgn()const{return y<0||(y==0&&x<0);}
};

int ix[MAX],iy[MAX];
ld ip[MAX];
void solve() {
    int n; scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", ix+i);
    for (int i=0; i<n; i++) scanf("%d", iy+i);
    for (int i=0; i<n; i++) scanf("%Lf", ip+i);
    int cx, cy;scanf("%d %d", &cx, &cy);

    point c(cx,cy);
    vector<point> v;
    for (int i=0; i<n; i++) {
        v.push_back({ix[i]-cx,iy[i]-cy,ip[i]});
    }
    sort(begin(v), end(v),[](const point& a,const point& b) {
        if(a.sgn()!=b.sgn()) return a.sgn()<b.sgn();
        return a/b>0;
    });
    ld ans=0,cur=0;
    int j=0,zero=0;
    for (int i=0; i<n; i++) {
        if(v[i].p<1)cur+=log10l(1-v[i].p);
        else zero++;
    }
    if(!zero)ans+=powl(10,cur);
    cur=0;zero=0;
    auto nxt = [&](int i){return (i+1)%n;};
    for (int i=0; i<n; i++) {
        while(v[i]/v[nxt(j)]>0) {
            j=nxt(j);
            if(v[j].p<1)cur+=log10l(1-v[j].p);
            else zero++;
        }
        if(!zero)ans+=powl(10,cur+log10l(v[i].p));
        if(i==j)j=nxt(j);
        else {
            if(v[nxt(i)].p<1)cur-=log10l(1-v[nxt(i)].p);
            else zero--;
        }
    }
    printf("%.10Lf\n", 1.L-ans);
}

int main() {
    // setbuf(stdout, NULL);
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        printf("Case #%d\n",i);
        solve();
    }
}