SCPC 2020 Round 2 후기

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

score

결과

  • 실력 맞추기: 100/100점
  • 고구마: 150/150점
  • 아르바이트: 200/200점
  • 안전운전: 0/250점
  • 삼각형의 거리: 0/300점

먼저 쓰는 느낀 점

본선 진출할것 같다. Round1은 풀이 및 후기였지만 이번거는 4,5번을 못풀었기 때문에 제목에 풀이는 뗐다. 그냥 후기만 작성. 모든 문제를 고생했다. 근데 어떻게 다 풀어냈기 때문에 큰 미련은 없다.

같은날 브랜디 코드네임B 2차대회도 2시~5시에 있었어서 정말 하루종일코딩만 하느라 힘들었다.


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

실력 맞추기

길이 $N$인 배열 $A$와 $B$가 있다. $A$와 $B$의 순서는 마음대로 바꿀 수 있다. 이 때 $A$의 수를 단 하나 원하는 아무 수로 바꿀 수 있다. $\sum_{i=1}^{N} \vert A[i]-B[i] \vert$의 최솟값을 구하시오.

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

실력 맞추기-풀이

  • 정렬
  • DP
  1. $A$와 $B$를 정렬한다.
  2. $A$에서 수를 아무거나로 하나 바꿀 수 있다는 것은 $A$에서 수 하나 $B$에서 수 하나를 제거하는 것과 같다.
  3. $dp[i][A에서 수를 제거][B에서 수를 제거]$ 이렇게 dp배열을 정의하고 dp테이블을 채우면 된다.

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

실력 맞추기-여담

4트만에 맞췄다. 정말 힘들었다.

코드를 보면 약간 이상한데 대회중이라 정리하면서 짜지는 못했다. 그렇게 어렵지는 않으나 제대로 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200'002;
ll a[N], b[N], n;
ll dp[N][2][2];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    for (int i = 1; i <= n; i++) {
        dp[i][0][0] = dp[i-1][0][0] + abs(a[i]-b[i]);
        if (i == n) break;
        dp[i][1][0] = min(dp[i][0][0], dp[i-1][1][0] + abs(a[i+1]-b[i])) ;
        dp[i][0][1] = min(dp[i][0][0], dp[i-1][0][1] + abs(a[i]-b[i+1])) ;
        dp[i][1][1] = min({dp[i-1][0][0]+abs(a[i+1]-b[i+1]),
                        dp[i][0][1],
                        dp[i][1][0],
                        dp[i-1][1][1]+abs(a[i+1]-b[i+1])
                        });
    }
    cout << min(dp[n][0][0], dp[n-1][1][1]) << '\n';
}

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

    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

고구마

길이 $N$의 정수 배열 $A$가 주어질 때, 연속된 구간의 합이 $M$ 이하인 것 중 최댓값을 구하여라.

  • 제한 조건
\[1 ≤ N ≤ 300,000\\ -10^{12} ≤ A[i] ≤ 10^{12}\]

고구마-풀이

  • Partial Sum
  • Set
  1. 부분합 배열 $P$를 생각해보자.
  2. $P[j] - P[i] \leq M(i < j)$ 를 만족하는 $P[j] - P[i]$ 의 최댓값을 구하면 된다.
  3. $P[j] + M \leq P[i]$의 P[i]의 최솟값을 구해서 답을 구할 수 있다. 이는 set::lower_bound를 쓰면 쉽게 할 수 있다.

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

고구마-여담

1번 문제보다 쉬웠다. 실제로는 부분합 배열도 안만들고 그냥 sum이라는 변수로 처리했다. 근데 좀 깔끔하게 짜려다 실수했다.

고구마-코드

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

ll a[300'001];
void solve() {
    ll ans = 0, sum = 0, n, M;
    set<ll> s;
    cin >> n >> M;
    s.insert(0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        s.insert(sum);
        auto it = s.lower_bound(sum-M);
        if (it != s.end()) {
            ans = max(ans, sum-*it);
        }
    }
    cout << ans << '\n';
}

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

    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

아르바이트

길이 $N$의 배열 $A$가 주어진다. 특정 위치의 수를 바꾸는 연산을 $Q$번 할 때, 각 연산마다 $A$에서 가능한 모든 길이 $K$의 부분 배열의 합의 중위값을 구하여라. 단, 중복된 합도 따로 센다.

  • 제한 조건
\[1 ≤ N ≤ 200,000\\ 1 ≤ K ≤ min(200, N)\\ 1 ≤ Q ≤ 2,000\\ 1 ≤ A[i] ≤ 100,000\]

아르바이트-풀이

  • Fenwick Tree
  1. 최대 업데이트 연산이 $O(QK)$ 번 일어난다는걸 알 수 있다.
  2. 수의 최대 크기는 $100’000 * 200 = 20’000’000 = MAXSUM$이다.

이 두 가지를 이용하여서 풀 수 있다.

풀이가 상당히 다양한데 좌표압축을 하는게 오히려 더 시간이 오래걸렸다.

k번째 수를 찾는건 이미 잘 알려져 있다. 백준 9426번

문제의 풀이보다는 최적화가 중요한 문제여서 세그먼트트리보다는 펜윅 트리르 사용하거나, median heap을 사용하는 것이 좋다.

시간 복잡도는 $O(QKlog(MAXSUM) + N)$ 이다.

아르바이트-여담

10트만에 맞췄다. ‘맞왜TLE’을 정말 고생했다. 근데 나만 고생한게 대회 참여자 대부분이 정말 고생한것 같다. 진짜 포기하고 싶었지만 끝까지 포기를 안해서 보상을 받은것 같다.

코드는 지우고 처음부터 다시짜서 나름 깔끔하다.

아브라이트-코드

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

const int MAX = 20'000'001;
int tree[MAX], a[200'001], p[200'001];

void update(int pos, int diff) {
    while (pos < MAX) {
        tree[pos] += diff;
        pos += pos&-pos;
    }
}

int sum(int pos) {
    int ret = 0;
    while (pos > 0) {
        ret += tree[pos];
        pos -= pos&-pos;
    }
    return ret;
}

int kth(int k) {
    int l = 0, r = MAX;
    while (l < r) {
        int m = (l + r) / 2;
        if (k <= sum(m)) r = m;
        else l = m + 1;
    }
    return l;
}

void solve() {
    memset(tree, 0, sizeof(tree));
    int n, K, Q; cin >> n >> K >> Q;
    vector<int> v;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = a[i] + p[i-1];
        if (i >= K) {
            v.push_back(p[i]-p[i-K]);
            update(p[i]-p[i-K], 1);
        }
    }
    int mid = (n-K+3)/2;
    cout << kth(mid);
    while (Q--) {
        int x, y; cin >> x >> y;
        int diff = y - a[x];
        a[x] = y;
        if (diff != 0) {
            for (int j = max(0, x-K); j < min(n-K+1, x); j++) {
                update(v[j], -1);
                update(v[j]+diff, 1);
                v[j] += diff;
            }
        }
        cout << ' ' << kth(mid);
    }
    cout << '\n';
}

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

    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << '\n';
        solve();
    }
}

안전운전

문제 제대로 읽어보지도 않았다.

삼각형의 거리

스몰은 작년 ICPC J번과 동치였다.

다행히 안 긁어도 본선 가는데는 문제 없을것 같았다.

라지는 스몰에서 볼록다각형 조건만 빠진것으로 좌표를 주고 계산해야한다.논문을 보고 잘 구현하면 된다고 한다.