$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

2020 SCPC Online Round 1 : 1-4번 풀이::::Gratus' Blog

2020 SCPC Online Round 1 : 1-4번 풀이

알고리즘 문제풀이/대회 후기, 문제풀이 2020. 8. 22. 14:08

SCPC (삼성전자 대학생 프로그래밍 대회) 를 처음 참여했다. 약간 K-코드잼 느낌? ㅋㅋㅋㅋㅋ

24시간 동안 치뤄지는 1차 예선을 거쳐서 적당한 인원이 2차에 진출하고, 다시 온라인 2차 예선으로 본선에 진출하는 시스템인데, 뭔가 여러가지로 시스템상 (다른 PS 대회에 비해) 독특한 점이 많다.

- 1차 예선은 Scoreboard를 볼 수 없고, 커트라인도 알려져 있지 않다. 정말 푼 사람수 보고 적당히 자르는 건가..?

- 부분점수를 받기 위해 버퍼해제 같은걸 직접 해야 한다. 이건 사실 왜인지 잘 모르겠다.

- 찾아보니 작년이나 재작년 예선에서는 휴리스틱 문제가 하나씩 나왔던것 같다. 올해는 없던데...

 

아무튼, 1번부터 4번까지는 만점을 받았고, 5번은 몇시간동안 코딩 사투 끝에 장렬히 전사했다. 사실 어떻게 풀지는 조금 알 것 같은데 나는 도저히 이런 이상한 풀이를 코딩할 자신이 없다.


문제 1. 다이어트

문제 설명

$A$ 식당과 $B$ 식당의 메뉴가 갖는 칼로리 값이 $N$개씩 주어진다. 이중 $K$일 동안, $A$에서 하나, $B$에서 하나를 먹어야 한다. 최대 칼로리를 섭취한 날의 칼로리 양을 최소화하려고 한다. $N \leq 50,000$.

 

풀이

찾는 답이 다음과 같음을 주장하고 증명한다. A와 B 배열이 모두 정렬되어 있다고 하자. 

$$max_{1 \leq i \leq k} (A[i]+B[k-i+1])$$

즉, A는 작은 것부터, B는 큰 것부터 그리디하게 먹는 전략을 의미한다. 이때의 최대값을 $X = A[t] + B[k-t+1]$라고 하자. 만약 저 조합에서 흐트러지되, $X$를 줄이기 위해 $A[t]$와 매칭되는 $B$의 값을 줄였다고 생각해 보자. 이때, $A[t]$ 보다 큰 원소가 $A$에는 $k-t$개 있고, $B[k-t+1]$ 보다 작은 원소가 원래 $k-t$개 있지만 방금 하나를 $A[t]$ 에게 줬기 때문에 $k-t-1$개밖에 없다. 결국 $A[t]$보다 큰 원소 중 하나는 $B[k-t+1]$ 보다 큰 원소와 매칭되게 되고, 최댓값이 $X$보다 커진다.

 

여담

내 입장에서 새벽 시간 (오전 9시) 에 일어나는 것은 너무 끔찍해서, 이 문제를 푸는데 필요 이상으로 오래 걸렸다.


문제 2. 카드 게임

문제 설명

카드 더미 $X$와 $Y$가 있고, 이중에서 한 더미를 골라 (NIM 게임 비슷하게) 맨 위에서부터 카드를 한 장 이상씩 번갈아가며 가져오는 게임을 한다. 단, 가져오는 카드에 쓰여 있는 수의 합이 $k$를 넘어서는 안 된다. 이때, $X$더미에 $i$장, $Y$더미에 $j$장이 남아 있을 때 사실 이미 승패는 결정나게 되는데, 이 승패를 판단하는 문제. $N, K \leq 3,000$.

 

풀이

2-1번 : 53점 풀이

백준의 돌 게임 류 문제와 비슷하게, 다이나믹 프로그래밍을 이용해서 할 수 있다. 다음과 같이 정의하자.

$\texttt{dp[i][j]} : $ $X$더미에 $i$장, $Y$더미에 $j$장이 남았을 때 선공의 승패. (1을 승리, 0을 패배)

선공 입장에서 한번 가져가고 나면 나는 후공이 된다. 즉, 내가 가져가고 나서 저쪽에 넘겨줬을때 dp값이 0이 되게 넘겨주고 싶다. 따라서, dp[i][j]의 점화식은 다음과 같다.

$$dp[i][j] = \begin{cases} 1 & ^\exists \text{  reachable  } n_i, n_j \text{  such that  } dp[n_i][n_j] = 0\\ 0 & \text{otherwise}\end{cases}$$

이 풀이는, 총 $O(n^2)$ 칸의 dp 테이블을 채워야 하고, 한번 채우기 위해 모든 Reachable 한 칸을 돌아야 하는데, Reachable 한 ni, nj가 최대 $O(k)$이고 $k \approx n$ 이므로 $O(n^3)$ 풀이이고, 53점을 받을 수 있다. 

 

2-2번 : 150점 풀이

위 풀이를 $O(n^2)$ 으로 줄이고 싶다. 여기서, reachable 한 칸이 $X$ 또는 $Y$ 방향으로 연속적임을 알 수 있다. 즉, (3, 2)에서 (1, 2)를 갈 수 있다면 (X에서 두장을 가져갈수 있으면) (2, 2) 도 갈 수 있다는 것이다. 또한, $O(n^2)$ 시간의 전처리를 통해, X와 Y 더미의 구간 합을 미리 구해 둠으로써 가능한 '최대한 먼 reachable ni, nj' 를 미리 모든 i, j에 대해 구해 놓을 수 있다.

이제, DP 테이블과 함께, DP 테이블의 X방향 부분합 테이블과 Y방향 부분합 테이블을 유지하자. 이 정보들을 가지고 있다면, dp[i][j]를 채울 때, 한번에 내 앞에 내가 갈수있는 모든 칸들 중 가고싶은 칸 (선공이 패배하게 되는 칸) 이 있는지 여부를 $O(1)$에 판정할 수 있다. 따라서, $O(n^2)$ 에 풀 수 있다.

 

여담

역시 새벽에 일어나서 (...) 53점 풀이를 자신있게 코딩하고 TLE를 받았다. 150점 풀이를 바로 생각했지만 설마 2번부터 이런 이상한걸 낼리가 없다는 혼자만의 망상에 빠져 꽤 오랜 시간동안 고민해봤지만 그냥 바로 짤걸 그랬다. ㅋㅋ 


문제 3. 사다리 게임

문제 설명

사다리와 쿼리 ...

가로선이 $k$개, 세로선이 $N$개 있는 사다리가 주어진다. 이때 사다리에 다음과 같은 쿼리가 주어진다.

$m(i, j)$ :  $i$번에서 출발해서 사다리를 타고 $j$번에 도착하기 위해, 부숴야 하는 가로선의 최소 개수. 즉, 가로선을 최소한으로 부숴서 $i$번에서 출발해서 $j$번에 오게 하라는 의미이다. 각 쿼리는 독립적이다.

원래는 고장인가? 아무튼 덜 반사회적인 방식으로 문제가 주어졌지만, 연습지에도 나는 꾸역꾸역 '사다리 부수기' 라고 써 놨더라

$k \leq 2,000$, $N \leq 1,500$.

 

풀이

3-1번 : 26점 풀이

$N \leq 20, k \leq 15$의 의도는 아마도 가능한 모든 '남은 가로선' 조합을 비트마스킹하고 시뮬레이션해서 $n2^k$ 시간에 $n^2$칸 테이블을 채우는 것이 아닐까? 생각해보지 않아서 모르겠다.

 

3-2번 : 79점 풀이

3-3번 : 150점 풀이

3-3번을 푸는 것이 3-2번보다 그렇게 어렵다고 생각되지 않는다. 실제로는 3-1도 생각해본적 없어서...

이 문제를 그래프로 모델링하려고 시도해 보자. 핵심 아이디어는, 세로선을 정점으로, 가로선을 간선으로 두되, 사다리에서 가로선이 한번 지나고 나면 정점이 두개로 쪼개진다는 것이다. 즉, 예시 그림을 하나 그려 보면 다음과 같다.

이제, 인접한 정점들을 간선으로 잇는다. 생각해 보면, 가로선을 타고 가만히 내려가는 것은 비용이 들지 않는다. 즉, 1->5를 갈 때는 비용 0으로 간선을 타고 내려갈 수 있다. 또한, 1번에서 4번에 가기 위해서는 (1, 4) 와 (2, 5) 사이의 가로선을 부수고 내려가야 한다. 따라서, 1번에서 4번으로 가는 간선은 1의 비용을 갖는다.

즉, (1, 4)와 (2, 5)의 첫번째 가로선 하나에 의해, (1->5, 비용 0), (2->4, 비용 0), (1->4, 비용 1), (2->5, 비용 1)의 간선 4개가 추가되게 된다. 우리는 각 세로선에 도착한다는 것이 몇번 정점에 도착한다는 것인지 (예를 들어, 2번 세로선에 도착하라는 말은 9번 정점에 도착하라는 뜻), 알고 있고, 출발은 저대로 번호를 매기면 원래 번호대로 출발할 수 있다.

결국 문제를 최단 경로 문제로 바꾸는데 성공했다. 이 문제에서 간선의 개수는 $4k$개, 정점은 $n+2k$개로, 정점 5500개, 간선 8천개의 그래프가 된다. 이 그래프에서 all-pair shortest path를 구하는 것은 불가능하다.

다만, 출발점은 1500개 (원래 있던 시작점들) 로 제한된다. 이를 이용하여 출발점을 줄여 다익스트라를 쓰려고 하면, 다익스트라 알고리즘의 시간복잡도가 E log E 임을 생각할 때, 1500 * 8000 * log 8000 풀이는 약간 불안하고, 특히 테스트케이스가 70개씩이나 되기 때문에 아마도 안 될 것 같다. (이게 79점 풀이인가? 라는 생각을 잠시 했지만, 여기서 한발 나가는게 별로 어렵지 않은것 같다. ㅋㅋ)

관찰해 보면 두 가지를 알 수 있는데, 둘 다는 필요 없고, 둘중에 하나만 알면 된다.

- 그래프가 DAG (Directed Acyclic Graph) 이다. DAG에서의 Shortest path는 Topological order를 따라 DAG DP를 수행함으로써 선형 시간에 구할 수 있고, 다익스트라 알고리즘을 아는 사람이면 아마 이것도 알 것 같다.

- 간선의 가중치가 0 또는 1이다. 이렇게 특이한 경우에서는, 선형 시간으로 줄일 수 있는 0-1 BFS라는 기법이 역시 잘 알려져 있다. 

나는 0-1 BFS가 훨씬 코딩하기 쉬울 것 같아서 후자를 사용했다. 0-1 BFS의 핵심 아이디어는, 어차피 간선의 가중치가 두가지밖에 없음을 알고 있으므로, priority queue를 이용하여 다음 정점을 로그 시간에 고르는 대신, 가중치가 0인 정점이 있는지 보고 (priority queue에서 어차피 맨 앞에 왔을 것이다) 하나 뽑거나 그렇지 않으면 1인 정점을 뽑는 것이다. 이를 쉽게 하기 위해, BFS에서 queue 대신 deque를 쓰고, 간선 가중치가 0일 때는 앞에, 1일 때는 뒤에 넣으면 된다.

 

여담

이 블로그에도 수십번 언급된 dlwocks31이 SCPC 처음 나가보는 나한테 며칠전에 '1차는 그냥 문제 자체가 쉬워서' '1차는 긴장할거 없음' 이라고 말했다. 긴장할게 없는건 맞는거 같지만 문제 자체가 쉽진 않은데, dlwocks31이 :god: 이거나 :evil: 이거나 둘중 적어도 하나인것 같다. 

오늘 이미 속으로 많이 욕했지만 블로그에 박제하기로 했다. 읽으러 오겠지? ㅋㅋ;;;; @dlwocks31 :fan:


문제 4. 범위 안의 숫자

문제 설명

$n$자리 숫자 $T$가 있다. 이중에 정수 $k \leq$가 주어졌을 때, $T$에서 연속한 $k$개의 숫자를 뽑아와서 만들 수 있는 모든 숫자들의 집합을 생각하자. 예를 들어, $T = 3141592, K = 3$이면 $\Set{314, 141, 415, 159, 592}$ 이다.

어떤 정수 $m$이 주어졌을 때, 시작위치 $a$를 하나 골라서, $[a, a+m]$ 에 이 집합의 수들을 최대한 많이 집어넣는 $a$를 찾으려고 한다. 여기에 추가로, $T$에서 딱 한 번, 한 자리의 숫자를 골라서 그 숫자를 1로 바꾸고 위 과정을 수행할 수 있다. 최대한 많이 집어넣을 때 몇개 들어가는지 찾기. 예를 들어 위 예시에서 $m = 200$이면, 그냥 넣으면 잘해봐야 141, 159, 314의 3개를 넣는데서 그치지만, 변경을 사용해서, 3141592를 3111592로 바꾸면, $\Set{311, 111, 115, 159, 592}$ 가 되고 111, 115, 159, 311을 딱 맞게 4개 넣을 수 있다. $n \leq 50,000, m \leq 1,000,000,000$.

 

풀이

4-1 : 39점 풀이

39점 풀이는 코딩 안 해봐서 잘 모르겠다. 복잡도 보고 뇌피셜로 쓰는거라, 훨씬 좋은 39점을 건지는 풀이 (간단한 뭔가) 가 있을 것 같기도 하다. 나는 4-2를 한번에 풀었기 때문에, 그 과정의 일부 아이디어를 나눠서 4-1만 맞을 수 있는 정도의 풀이를 하나 제시하는 상황이다. (4-2 풀이의 설명을 위한 포석..)

구간의 끝점을 기준으로 생각하자. 어떤 수 $x$가 집합에 존재한다는 것은, 구간의 끝점이 $[x, x+m]$ 사이에 있을 때, +1만큼의 이득을 제공하겠다는 말과 같다. 이때 최대한의 이득을 얻는 것 (이득 값이라고 하자)을 목표로 한다. 여기서, $m$이 매우 클 수 있으므로, 실제로 $m$칸의 배열을 잡는 것은 말도 안 되고, 다음과 같이 생각하자.

- 이득 값을 직접 들고 있는 대신, 이득 값을 나중에 계산할 수 있는 정보를 들고 있자.

즉, 내가 잡은 구간의 끝점이 $x$를 넘는 '순간' +1의 이득을 제공하고, $x+m+1$에서 아까 준 이득을 빼앗는다고 생각해 보자. 이 배열을 앞으로 $S$ 배열이라고 부를 것이다.

 

예를 들어, $\Set{314, 141, 415, 159, 592},m = 200$ 에서는, $S$배열을 (314, +1), (515, -1), (415, +1), (616, -1) 처럼 생각할 수 있다. (실제로는 $S[314] = 1, S[515] = -1$처럼...) 나중에 이 배열에서 실제로 내가 얻는 값을 구하는 방법은, 조금 생각해 보면, $S$ 배열의 임의의 contiguous subarray sum을 내가 실제 값으로 만들 수 있음을 관찰하자. 어차피 '314를 넘는 순간 +1', '515를 넘으면 -1' 처럼 주어져 있으므로, 원하는 곳에서 출발해서 앞으로 달려나가면서 이득은 많이 보고 그 이득 본 값을 잃기 전에 끊으면 된다. 이 풀이에서 이해해야 하는 것은 크게 두 가지이다.

- '구간에 대한 정보' 를 '점 2개' 로 압축했다.

- 원래는 $m$ 길이의 구간을 골라야 했는데, 위와 같이 압축하고 나면, 연속된 부분배열은 아무렇게나 골라도 된다. 

(참고로, 이 방법은 직사각형의 합집합 같은것을 구할 때, 직사각형의 왼쪽 끝에서 +1, 오른쪽 끝에서 -1 하는 식으로 사용한다. 스위핑 기법이라고 생각하면 간단하다. 사실은 '선분들' 이 주어지고, 선분에 올라갈때마다 +1, 내려올때마다 -1 하고 있는 것이다)

당연한 말이지만, 값이 엄청 크기 때문에 모두 좌표압축해야한다. 위 $S$배열도 실제로는 압축되어야 한다. 압축해야 하는 숫자는 모두 $2(n+kn)$ 개인데, 한번에 $2k$ 개씩 새로운 숫자가 생기는데 $n$번의 업데이트가 있다.

 

이제, 우리는 '최대 부분합 배열' 문제로 주어진 문제를 환원했다. 구체적으로는, 한번 최대 부분합을 구하는데 $O(n)$ 시간이 걸리는데 (Kadane's algorithm), 처음과 $n$번의 업데이트 과정에서 총 $n+1$번 부분합을 구하는 것이므로, $O(n^2)$ 시간에 풀 수 있다. 좌표압축에 $O(kn \log{kn})$ 시간을 사용했으므로, 시간 복잡도는 $O(kn \log{kn} + n^2)$ 이고, $k \leq 9$ 이므로 $O(n^2)$ 이라고 보면 된다.

 

* 아마도 lower bound 등 이분탐색을 적절하게 쓰는 39점 풀이가 훨씬 간단할 것이다. 다만 그 풀이로 나머지 161점을 향해 발전시키는 방법은 잘 모르겠다. 내 풀이는 그냥 한가지 방법일 뿐이니 너무 이상하게 생각하지 말자..!

 

4-2 : 200점 풀이

위 풀이 그대로 진행한다. 그런데 무려 161점이 걸려 있다. ㅋㅋㅋ 

위 풀이에서 시간을 줄일 수 있는 부분을 관찰하자. 최대 부분합 배열을 잘 보면, 한번 업데이트 쿼리가 들어올 때마다 $2k$개의 수가 새로 생기고 $2k$개가 없어지는데, 겨우 40개 남짓 업데이트했을 뿐인데 5만개짜리 배열의 최대 부분합 배열을 처음부터 다시 구해야 하는 것이 매우 기분 나쁘다.

적절한 자료구조를 이용해서, point update가 가능한 최대 부분합 배열을 작성하자. 이는 세그먼트 트리로 할 수 있고, 이 블로그에 이를 이용한 문제인 KOI 2014 금광을 포스팅할 계획이 있었지만 끝없이 미뤄져서 하지 않고 있다. ㅋㅋㅋ

요점은, 세그먼트 트리를 관리하는데, 아래 두 노드에서 위로 올라올 때 단순히 합만 갖고 있는 대신 추가적인 정보를 관리하는 것이다. 그때 썼던 말을 그대로 가져오자면,

 

대략적으로는 $(a, b)$ 의 중간값을 $c$ 라고 할 때, $(a, c)$ 와 $(c+1, b)$ 로 나눈 다음 다음 네가지 값을 계산해야 한다.

- '왼쪽 끝' 에서부터 시작해서 최대 부분합

- '오른쪽 끝' 에서부터 시작해서 최대 부분합

- 그 구간의 최대 부분합 (반을 잘라서 분할정복으로 업데이트)

- 그 구간의 합

 

총 $4nk$번의 업데이트 연산, $n+1$번의 쿼리를 쓰는데, 쿼리 자체는 실제로는 구간을 재귀적으로 돌 필요도 없이 전체 배열의 최대 부분합만 가져올 것이므로 $O(1)$에 되고, 업데이트 한번에 $O(\log n)$ 이 걸린다. 그러나 $4nk\log{n}$ 인것 치고는 나는 아주 많이 (제한 시간 10초 중 7.7초인가?) 타이트하게 걸리던데, 내 구현이 안 좋은 건지, 이 풀이가 의도된 정해가 아닌 것인지 잘 모르겠다. 금광 때 보니까 내 구현이 그렇게 좋은 것 같지는 않다. 언젠가 비재귀 세그로 고쳐놔야지....


문제 5. 우범지대

문제 설명

2차원 평면상의 점 $n$개와 내 위치 $(x, y)$가 주어진다. 각 점마다 '켜질 확률' 값이 있고, '켜진 점들'을 모아서 Convex hull을 만들 때, 이 Convex hull이 내 위치를 포함할 확률을 구하는 문제.

 

풀이

전혀 모르겠다. ㅋㅋ

전혀 모르는거 까진 아니고, 반대로 '안 되는 확률' 을 구하고 싶다는 점, 안되는 확률을 구하려면 전체 평면을 반 잘라서 반평면이 텅 비어있어야 한다는 점 등등을 이용해 몇시간 정도 고생을 해봤지만 본래 기하에 약간 약하고 이런 쪽 테크닉을 거의 몰라서 3시간 넘게 구현 노가다를 하다가 끝났다. 마지막으로 생각한 풀이는 전체 점들을 각도순으로 정렬한다음 180도가 넘지 않는 두 점을 택하고, 그 두 점 바깥쪽이 텅 비어 있고 그 두 점이 켜져 있다고 놓고 그 확률을 구하는 식으로, 두 점을 택하는 부분을 투포인터로 잡아서 $O(n)$ 비슷하게 계산할수있지 않을까 싶었는데 구현이 너무 복잡해서 그만두기로 했다. 특히 p = 1이 되는게 구현상 너무 꼬인다 ㅜ


후기.

1. 생각보다 문제가 많이 어렵다. PS 실력이 집나가서 그렇게 느끼는 걸수도 있고...

2. 아침에 일어나는것은 생각보다 더 끔찍하다. 학교는 어떻게 다녔지?

3. dlwocks31 :fan: :blobfist:. 다음에 만날때 봅시다 ^^

4. 재밌었다. 24시간이라서 조금 루즈하지만, 실제로는 3시간 정도 걸렸음에도 사실 3시간 대회였으면 D에 도전해서 저 풀이를 생각해 내지 못했을 것 같다. 루즈하기 때문에 해볼수있는 것들이 있는것 같다.

5. 휴리스틱 문제가 나온다고 하던데, 나는 약간 휴리스틱 알고리즘에 애증이 좀 있어서 재밌을것 같다고 생각했다. 특히 24시간씩이나 되는 긴긴 시간동안 딱히 집중할게 없을때마다 조금씩 수정해보면서 휴리스틱 점수 긁는 맛이 짜릿할것 같았는데 그게 없는건 좀 아쉽다. ㅋㅋㅋㅋㅋㅋㅋㅋ

6. 문제가 많이 어려웠음에도 불구하고, PS판이 갈수록 고여가고 있어서 밤에 이 포스팅을 쓸 때만 해도 85명 정도가 4번에서 만점을 받았다. 수상은 고사하고 본선 진출도 난항을 겪을 예정이다. 특히 본선때까지 이런저런 일로 바빠서 공부할 시간이 없는것도 있고...

admin