삼성 SCPC 2차 예선 후기

• Before Contest
• 문제 1 : 수열연산
• 문제 2 : 반 협동 게임
• 문제 3 : ABC - Subtask 2
• 문제 5 : 황금카드
• 문제 4 : 직사각형
• 다시 3번 : ABC
• 남은 시간

TL, DR: SCPC 참가 3년만에 본선에 진출하게 되었습니다

대회 자체에 대한 이야기는 작년 2차 후기, 작년 1차 후기 에 많이 썼으니 2차 예선 얘기만 하겠습니다 :)

Before Contest

작년과 재작년 SCPC 2차예선은 모두 3번 문제의 벽을 넘지 못했습니다. 이유를 대충 분석해 보자면…

• 구현 난이도 : 전반적으로 제가 구현문제에 약한 편인데, 두 라운드 모두 구현이 상당히 어려웠습니다.
  • 2020년에는 Erasable heap 등 적절한 자료구조를 이용, 상수를 많이 줄여야 했습니다. 저는 여전히 부분점수를 받지 못한 실수로 떨어졌다고 생각합니다. ㅋㅋ
  • 2021년에는 $O(n^2)$ 시간 에 DP로 풀 수 있는 문제를 $O(n^2 \log n)$ 시간 FFT로 비벼보다가 망했습니다. ㅋㅋ… 변명하자면, 원래 문제도 구현은 상당히 어려웠습니다. Platinum 2 정도 난이도 DP라고 생각합니다.
• 대회 시간 12시간 : 12시간이라는 대회 시간이 워낙 길다 보니, 5시간 정도부터는 시간이 너무 많아서 늘어지고 집중력이 떨어지게 됩니다.
• 제출 기회 10번 : 보통 PS 문제를 풀면서 10틀을 쌓는 경우가 흔하지는 않지만, 위 두가지가 합쳐지면 굉장히 빠르게 쌓게 됩니다. 이게 또 문제가, 후반에 대회가 4시간 정도 남았을 때 기회가 2번 뭐 이렇게 남으면 정말 피말리게 됩니다.

그래서 이번 SCPC 2차는 Brute-force naive를 짜고, stress-test를 해보고 코드를 내겠다 는 놀라운 전략을 들고 들어갔습니다. 또한, 대회 중간에 다른 장소 (집 -> 카페) 로 20분 정도를 이동하여 대회를 치기로 했습니다. 전자는 제출횟수를 아끼기 위함이고, 후자는 12시간 중간에 흐름을 한번 끊어서 집중력을 리젠하기 위해서인데… 정상적인 CP대회에서는 불가능한, 12시간 5문제 라운드용 해법입니다.

다만 Bruteforce는 실제로는 쓸일이 없었는데, 이는 후술하겠습니다.

대부분의 2차 대회 관련 블로그 포스팅 JusticeHui님 을 비롯한 여러 실력자분들이 풀이를 정갈하게 정리해주셨으니, 저는 제 제출을 그대로 따라가 보려고 합니다.

• 시간은 대회 시작후 경과시간, 점수는 문제점수와 전체 점수이며 난이도는 예상으로 제가 매긴 것입니다.

문제 1 : 수열연산

문제요약 수열 $X$와 정수 $k$ 가 주어지고, 수열에 대한 $(i, j)$ 연산은 $j-i+1$ 비용을 지불하여 $x_i \dots x_j$ 를 1만큼 증가시킨다고 정의합니다. $\min(X) \geq k$ 로 만들기 위해 필요한 최소 비용 구하기.

Tag : Two pointer
Difficulty (100점 기준) : G5
Time    Prob        Total
00:12   (  0/150)   (  0/1000)
00:13   (100/150)   (100/1000)

• 결국, 최소값을 k까지 끌어올릴 만큼 의 연산이 필요함을 알 수 있으며, 최적값은 “아직 $k$에 미치지 못한 원소들을 모두 커버하는 구간” 에 계속 연산을 수행하는 것임을 알 수 있습니다.
• 따라서, 현재 $k$에 미치지 못하는 최대/최소 원소를 투포인터로 저장하고 이를 업데이트하면 됩니다.
• 매 iteration마다 구간의 길이를 1씩 줄일 수 있으므로 $O(n)$ 에 풀 수 있습니다.

놀랍게도 제출에서 제출 양식 (# 붙이기) 를 실수해서 1번 틀렸습니다. ㅋㅋㅋㅋ…

문제가 쉬웠기 때문에 Bruteforce는 짜지 않았습니다.

문제 2 : 반 협동 게임

문제요약 학생들 $N$명이 순서대로 주어지며, 같은 반 학생 둘을 짝지으면 두 학생이 빠져나갑니다. 이때, 두 학생 사이에 있던 학생 수만큼의 점수를 얻습니다. 최대한 많은 점수 얻기.

중간에 학생이 빠져나가면 그만큼 얻을 수 있는 점수가 감소함에 주의해야 합니다.

Tag : Segment tree
Difficulty (150점 기준) : G1
Time    Prob        Total
00:36   (150/150)   (250/1000)

• 일반적으로, 가능한 한 멀리 있는 Pair를 매칭해야 이득입니다.
• 같은 반 학생들이 여럿 있다면, 최대한 바깥쪽부터 빼내면 됩니다. 이는 다시 말해, 가장 왼쪽과 오른쪽을 묶어 빼내는 것을 반복하면 됩니다.
• 이제 다른 반들 간에 무엇을 먼저 처리할지 생각해 봅시다.
• 잠시 “빠져나간 자리” 를 고려하지 않고 문제를 푼다면, 모든 Pair가 이미 정해져 있습니다.
• 빠져나간 자리에 해당하는 점수는 얻지 못하는 점수이며, 이는 Inversion counting 형태로 생각할 수 있습니다.
• 결국…. 학생들이 a..b...a...b 형태로 나타날 때, a를 b보다 항상 먼저 처리해도 됩니다.
• 따라서, 왼쪽부터 보면서 “나와 같으면서 가장 오른쪽” 에 있는 학생과 매칭하면 됩니다.
• 중간에 빠져나간 자리의 개수를 다이나믹하게 알아야 하므로, 이를 Fenwick Tree 등으로 계산하면 됩니다.

저는 개인적으로 Fenwick Tree 자료구조 자체가 Segment Tree보다 훨씬 어렵고 실수하기 쉽다고 생각합니다. Codeforces 기준 2100을 찍은 지금도 솔직히 Fenwick Tree를 외워서 구현하지 못하는 제 처참한 상태 때문이기도 하지만… 그래서 가급적 Fenwick Tree를 회피하는 편인데, SCPC 특성상 또 상수 최적화가 필요할지도 모른다는 생각에 BOJ 블로그 에 나온 fenwick tree를 때려넣었습니다.

결과적으로는 segment tree도 별 무리 없이 통과했던듯 합니다. 역시 문제가 쉬웠기 때문에 Bruteforce는 짜지 않았습니다.

쉬운 2문제를 푼 다음, 3, 4, 5번을 쭉 읽었습니다. 3번의 경우 아 이번 SCPC도 나한테 쉽지 않겠다 는 생각이 들게 만들었고, 4번과 5번은 두번째까지는 쉬웠으나 마지막 메인 태스크는 손대기 어려워 보였습니다.

문제 3 : ABC - Subtask 2

문제요약 간선에 A, B, C가 써있는 방향그래프가 주어집니다. 임의의 경로 (중복 간선 사용을 허용함) 를 잡아 ...ABCABCABCA.... 형태의 문자열을 최대한 길게 만들어야 합니다. ($A$로 시작할 필요는 없으나, 순서는 지켜야 함) 간선을 밟으면 반드시 그 문자를 문자열 뒤에 붙여야 하지만, $K$ 번의 스킵 (문자를 붙이지 않고 간선만 사용) 이 허용됩니다.

이 문제는 독특하게도, $K = 0, 1, 2, \infty$ 에 대해 문제를 풀어야 하는데…

• $K < \infty$ 와 $K = \infty$는 사실 꽤 많이 다른 문제이고 풀이가 상당히 다릅니다.
• 서브태스크 구성이 (SMALL / $K = 0$ / $K = \infty$ / 전체) 로 되어있었습니다.
• 솔직히 SMALL을 푸는 풀이는 전혀 모르겠습니다. 그래서 Bruteforce도 짤 수 없었고, 우선 $K = \infty$를 도전했습니다.

Tag : Graph, DP
Difficulty (Subtask 2, 34점 기준) : P5
Time    Prob        Total
01:50   (  0/200)   (250/1000)
03:54   ( 34/200)   (425/1000)

점수(와 시간)의 갭은 중간에 5번을 긁고 왔기 때문입니다.

먼저 $K = 0$ 인 경우를 생각해 보겠습니다. 스킵이 불가능하다는 것은, 다시 말해 ABC 순서대로 경로를 돌아야만 한다 는 것입니다.

• 문제 자체는, 정점 나누기 트릭을 쓰는 형태입니다. 즉… 각각의 (정점 번호, 마지막으로 먹은 알파벳) 순서쌍을 정점으로 두고 이 순서쌍들 사이를 적절한 간선으로 잇는 것입니다. 원본에 $(1, 2, A)$ 간선이 있었다면 이는 $(1, C)$ 정점에서 $(2, A)$ 정점으로 간선이 이어지는 형태가 됩니다.
• 이렇게 바꾸면 더이상 알파벳을 순서대로 먹어야 한다는 것을 고려하지 않을 수 있어, 문제를 크게 단순화할 수 있습니다.
• 그러면 결국 방향 그래프에서 최장 경로의 길이 비슷한 것 (각주¹ 참고) 를 구하는 문제가 됩니다. 여기서는 다음과 같은 방법이 가능합니다.
  • 만약 그래프가 Cycle을 포함하고 있다면, 답은 $\infty$ 입니다.
  • 만약 Cycle이 없다면 그래프는 사실 DAG이며, DAG에서 가장 긴 경로를 구하는 것은 DP로 어렵지 않게 가능합니다. 트리의 깊이 를 구할때 우리는 $i$번째를 루트로 하는 서브트리의 깊이를 저장해놓고 DP를 돌리는데, DAG에 대해서도 똑같이 할 수 있습니다. ²
• Cycle을 $O(V+E)$ 에 구하는 방법은 CLRS 책에도 나와있는 White-Gray-Black 마킹으로 가능합니다. (Lemma 22.12)
  어렵지 않으면서도 재밌으므로 간략히 소개합니다. 이미 방문한 정점을 회색으로, 방문이 끝난 정점을 검정색으로 마킹하고 DFS를 돈다고 생각하면, cycle이 있을 필요충분조건은 DFS 트리에서의 Back edge 이므로, 아직 방문이 끝나지 않은 회색 정점을 dfs 도중에 또 만나게 되는 경우 사이클이 있는 것임을 알 수 있습니다. 코드 참고.

    void cycle_detection(int v){
        color[v] = 1; // Gray
        for (int w : graph[v]){
            if(color[w] == 1)
                found_cycle = true;
            if(color[w] == 0)
                cycle_detection(w);
        }
        color[v] = 2; // Black
    }
  

• DAG DP도 $O(V+E)$ 에 할 수 있으므로, 전체 문제를 $O(V+E)$ 에 풀 수 있습니다.

작성 순서를 점수가 올라가는 Chronological order를 따르려고 했는데, 그러지 않은 이유는 01:50분 제출과 03:54분 제출은 2시간의 갭이 있음에도 사실 거의 같은 코드이기 때문입니다. 서브태스크를 하나씩 긁기 위해 풀지 않을 서브태스크 ($K \neq 0$) 이 들어오면 0을 리턴하도록 했는데, 입력을 다 받기도 전에 0을 리턴해버려서 이후 입력을 받는게 꼬였습니다. ㅋㅋㅋ…. 멀티-테캐형 코포 문제에서 자주 있는 실수입니다. ㅎㅎ..

문제 5 : 황금카드

문제 요약 : Coupon collector’s Problem 에서, 각 카드의 확률이 주어져 있습니다. $k$ 번의 뽑기를 했을 때 서로 다른 카드 종류의 기댓값 $E_k$ 구하기. 단, $k = 1 \dots K$ 에 대해 전부 구해야 합니다.

3번을 구현하다가 한번 틀리고, 이전에 봐놓은 5번을 긁으러 왔습니다.

Tag : Combinatorics (141점 기준)
Difficulty (Subtask 2, 141점 기준) : G4
Difficulty (Full Problem) : *Ruby*
Time    Prob        Total
02:18   (141/300)   (391/1000)

• 먼저, 각 카드의 확률을 $p_1 \dots p_N$ 이라 하면, $k$ 번의 뽑기를 하고도 $i$번째 카드를 뽑지 못했을 확률은 $(1 - p_i)^k$ 입니다.
• 기댓값의 선형성에 따라, 우리가 구하는 값 은 사실 $\sum_{i = 1}^{N} 1 - (1 - p_i)^k$ 입니다.
• 따라서 $E_k$ 값 하나를 계산하는 것은 $O(N \log k)$ 에 가능하고 (로그 시간 거듭제곱), $k = 1 \dots K$ 에 대해 전체를 $O(NK \log K)$ 에 구할 수 있습니다.
• 이걸로도 아마 서브태스크 2를 통과할 수 있어 보이지만, 사실 바로 이전의 계산결과를 가지고 있다면 $E_{k-1}$ 를 구하는 중간 과정으로부터 $E_k$ 를 $O(N)$ 시간에 구할 수 있어서 전체 문제를 DP-틱하게 $O(NK)$ 에 풀 수 있습니다.

메인 태스크 (159점짜리) 는 이 문제를 $N = 50,000, K = 250,000$ 에 대해 풀기를 요구합니다. 매우 난감해 보였고, 일단 던져두었습니다.

문제 4 : 직사각형

문제 요약 : $1 \dots N^2$ 까지의 수들을 $N \times N$ 정사각형에 permutation 해놨을 때, $[a, b] \times [c, d]$ 를 잡아서 이 안의 수들이 연속하는 경우의 수 세기.

Tag : Range Minimum Query (62점 기준)
Difficulty (Subtask 2, 62점 기준) : P5
Time    Prob        Total
05:00   ( 62/300)   (487/1000)

• 문제를 $O(N^4)$ 시간에 풀 수 있다면 62점을 받을 수 있고, 어렵지 않습니다.
• 가능한 직사각형의 후보는 $O(n^4)$ 개입니다. (왼쪽 위와 오른쪽 아래 점을 고정하면 직사각형 후보 하나)
• 따라서, 직사각형 하나를 $O(1)$ 에 판정할 수 있으면 됩니다.
• 직사각형 안에 들어 있는 원소의 개수를 알고 있으므로, 최대/최소값을 빠르게 구하면 됩니다.
• $O(k \log k)$ 시간에 Preprocessing을 하면 구간의 최소값을 $O(1)$에 구할 수 있는 RMQ가 있는데, 이것의 2D 버전을 구현하면 됩니다.
  • RMQ의 핵심 아이디어는 Sparse table에 모든 길이 $2^k$ 짜리 구간의 최소값을 preprocessing하는 것입니다.
  • 그러고 나면, 쿼리 구간을 앞뒤 $2^k$ 짜리로 덮은 다음 이들을 확인하는 방법으로 풀 수 있습니다.
  • 합과는 달리, 덮을 때 구간이 겹쳐도 상관이 없기 때문에 구간을 재귀적으로 찾아갈 필요가 없어 $O(1)$에 쿼리가 가능합니다.
  • 2D로 하면, $2^i \times 2^j$ 크기 직사각형들을 preprocessing하고…
  • 쿼리 직사각형을 전처리한 직사각형 네개로 덮어서 확인하면 될것 같습니다.
• 당연히 이거 구현할 줄은 모르기 때문에, 공개 라이브러리를 찾아 오랜 시간을 헤맨 끝에 가져올 수 있었습니다. (ㅎㅎ….)
• 사실 이 위에 써있는 내용까지는 알고 있었는데, 어차피 1시간을 라이브러리 찾아 헤맬 거였으면 그냥 근성으로 짰으면 해볼만 하지 않았을까 싶긴 합니다. 체력을 아껴서 3번을 풀었다고 생각하기로 했습니다.

여기까지 풀고, 계획의 일부였던 나가서 해야겠다 를 시전했습니다. 적당히 아무 카페나 상관없다고 생각하긴 했는데…. 환경이 그리 좋지는 않았습니다.

어차피 이시점에서 이번 대회의 성패는 결국 3번 나머지 서브태스크를 풀 수 있느냐 에 걸려 있다는 것은 사실 확실해 보였고, 어디든 기분만 전환된다면 크게 중요하진 않았습니다. 그래도 비교적 예상대로 대회가 흘러갔습니다.

다시 3번 : ABC

Tag : Strongly Connected Components, DP, Graphs
Difficulty (250점 기준) : P2
Time    Prob        Total
07:14   ( 76/200)   (529/1000)
08:55   (200/200)   (653/1000)

$K = \infty$ 와 $K = 1, 2$ 가 남았습니다. 먼저 $\infty$를 해결해 보겠습니다.

• 무한 번 스킵을 허용한다는 것은, 다시 말해 원할 때만 알파벳을 먹어도 좋다는 뜻이 됩니다.
• 역시 답이 $\infty$ 인 경우부터 생각해 보겠습니다. 무한번 스킵이 가능하다면 Cycle 상에서 순서가 상관이 없어집니다 (계속 돌면서 원하는것만 뺴먹으면 되므로) 따라서 사이클이 BACBAC 더라도 이를 돌면서 ABCABC...를 만들어낼 수 있습니다.
• 그런데, 어차피 이렇게 할거라면 사실 Cycle에 한정될 필요는 없어 보입니다. 정확히는 그래프 상에서 무한히 오갈 수 있는 정점들의 집합 을 고려하는 것으로 충분하고…
• 이는 Strongly Connected Component입니다! 따라서, 어떤 한 SCC에서 A, B, C를 모두 발견할 수 있다면, 그 SCC에 앉아서 A, B, C를 계속 순서대로 받으면 무한히 긴 문자열을 얻을 수 있어 답이 $\infty$ 입니다.
• 이제, 답이 유한한 경우를 풀면 됩니다. 위 경우를 걸러냈으므로, SCC로 정점을 모두 압축해서 그래프를 DAG로 바꾸면 각 SCC-정점을 통해 (A, B, C) 중 최대 2개를 먹을 수 있게 됩니다.
• 정점과 간선이 모두 값을 갖는 것이 부담스러우므로, 간선 사이에 정점을 집어넣어 정점들만 알파벳을 갖도록 문제를 바꾸면, 정점마다 (A, B, C) 중 1개에서 2개의 알파벳을 가진 DAG에서 최대 길이 문자열을 찾는 것이 됩니다.
• 이제, DP[i][j] 를 $i$번 노드를 루트로 하는 DAG에서, $j$번 알파벳으로 시작하는 최대 경로의 길이 로 정의하면 DAG DP가 가능합니다.
• SCC는 Tarjan 알고리즘으로 $O(V+E)$에 구할 수 있고, 정점 압축 - 중간에 정점 넣기 - DAG DP는 모두 각각이 $O(V+E)$ 시간이므로 $O(V+E)$ 에 전체 문제 해결이 가능합니다.

구현이 굉장히 까다로웠습니다. 사실 이 문제를 풀 자신은 없었는데 용케 76점을 한번에 맞은듯 합니다.

이제, $K = 1, 2$를 해결하기 위해서는 $K = 0$의 풀이 (Cycle찾기 + DAG DP) 를 확장합니다. $K = 0$ 을 풀기 위해 우리는 이미 정점을 3배로 ($(1, A)$ 형태) 늘렸습니다. 이런식으로 유한 번 간선의 일부에 대해서만 특별한 연산이 주어지는 경우도 비교적 흔하며, 마찬가지로 특별한 연산을 몇 번 썼는지에 따라 정점을 더 분할해서 풀 수 있습니다. ³ 따라서 정점을 $(1, A, 0)$ 형태로 몇번을 스킵했는지에 따라 추가해 줍니다.

• 원본 그래프의 $(1, 2, A)$ 간선이 $(1, C)$ 에서 $(2, A)$를 이었다면, 이는 이제 $K+1$배 더 split 된 그래프에서는 $(1, C, s)$ 에서 $(2, A, s)$ 을 이어주게 됩니다 ($s \in \Set{0, 1, \dots K}$)
• 또한, 현재 간선을 스킵하기로 선택하게 된다면 내가 지금 가지고 있는 ‘마지막 알파벳’을 유지한 채로 위치만 옮겨가는 것이므로, $(1, a, s)$ 에서 $(2, a, s+1)$ 로도 이어주면 됩니다 ($a \in \Set{A, B, C}$)
• 각 간선은 최대 $(K+1) + 3$ 부가 복사되게 되고, 정점은 $3(K+1)$부가 복사되게 됩니다.
• 이제 스킵을 아예 고려할 필요가 없고, $K = 0$ 의 풀이를 따라가면 되므로 $O((V+E)K)$ 시간에 문제를 해결하게 됩니다.

사실 $K = 1, 2$ 는 $K = 0$을 풀고 나면 그리 어렵지는 않습니다. $K = \infty$가 문제 난이도의 핵심인것 같네요. 다만 저는 구현상의 실수로 1시간 반정도가 더 걸렸는데, $K = 0$ 풀 때 미리 짜놨어도 됐을것 같습니다.

남은 시간

만점자 수를 보니 진출은 가능해 보였으므로, 남은 시간 동안은 5번에 투자했습니다. 결국 구하는 값이 $\sum_i x_i^k$ 형태임에 주목하면 이를 Power sum Symmetric Polynomial 로 생각할 수 있고… 이를 빨리 구하기 위해서는 Elementary symmetric polynomial $e_1 \dots e_n$ 을 구한 다음, 이들을 Newton-Girald Formula에 의해 짜맞춰서 구할 수 있다고 생각했습니다. 우리는 $e_i$들을 모두 구하는 데 FFT를 Binary tree 위에서 수행함으로써 $O(n \log^2 n)$ 시간에 구할 수 있고, Newton-Girald forumla도 일종의 convolution이므로 convolution을 거꾸로 돌리는, 대략 다항식 나눗셈 같은 컨셉으로 진행해서 $O(K \log K)$ 에 후반부 연산이 가능하다는 생각이 들었지만 남은 시간에 이걸 구현하지는 못했습니다.

전반적으로 풀 만한 문제는 다 풀었고, 못 풀었을 문제는 못 푼 대회였던 듯 합니다. 가장 마음을 비우고 치렀던 SCPC에서 본선 진출해서 굉장히 묘하네요. 본선도 재밌게 즐길수 있었음 좋겠습니다 :)