제 3회 소프트콘 후기

총평

재밌는 대회. https://store.steampowered.com/app/1372810/Teamfight_Manager/ 많은 관심 부탁드립니다.

 

대회 후기

2등 했다.

일단 A부터 쭉 푸는 데까지 풀어보자 하면서 시작했다. A에서 2번을 틀리면서 산뜻하게 출발했다.

B를 봤는데, 운 좋게도 B에 나온 퍼즐 게임이 내가 폰으로 많이 하던 게임이랑 거의 똑같아서 문제를 본 즉시 구현을 할 수 있었다. 다들 B 뛰어넘고 나중에 풀던데 ㅋㅋㅋ 그래서 퍼솔을 먹었다.

<Exponential Idle>이라는 게임의 미니 게임으로 붙어 있는 Torus Puzzle.

C도 다행히 풀이가 금방 생각나서 (비슷하게 푸는 문제를 본 거 같은데.. 아닌가) 금방 짰고, D 역시 비슷한 문제를 몇 번 풀어봤다면 바로 풀 수 있는 문제였다.

이제 E를 봤는데, 처음에 잘 생각이 안 났다. 그러다가 자료구조 쓰는 이상한 풀이를 구현했는데 예제가 안 나왔다.. 사실 그냥 완전 틀린 풀이였다. 퍼솔이 무려 16분만에 나온 문제였는데, 뭔가 이상하다 싶었지만 풀이가 계속 안 떠올라서 결국 옆으로 넘어갔다.

F랑 G랑 H 중에 그나마 풀려 있던 게 H라서 봤는데, 이것도 또 내가 예전에 풀어서 블로그에 올린 코드포스 문제(이 글 D번)랑 상당히 비슷하게 생겼다. 비슷한 접근 방식을 취하니 금방 풀 수 있었다.

이제 E랑 F랑 G가 남았는데 셋 다 잘 모르겠어서 한참을 생각했다. 심지어 중간에 대대 건물 방역한다고 밖으로 내쫓겨서 한 30분 동안 생각만 했는데도 잘 모르겠었다. 결국 G랑 F를 긁는 코드를 먼저 짜기로 하고, G를 좀 뚫으려다가 잘 안 돼서 포기했다. E를 계속 봤는데 계속 모르겠었다...

저녁을 먹을 시간이 돼서 일단 올라갔는데, 갑자기 E의 풀이가 생각났다. 저녁 먹고 와서 못 짜고 끝나면 너무 아쉬울 거 같아서 저녁도 skip하고 바로 싸지방으로 다시 달려가서 짜서 냈다. 맞아서 정말 다행이었다. 남은 시간에는 그냥 G에 이상한거 좀 더 내다가 끝났다. 

 

문제별 풀이

A

k를 고정하고, 점프를 k번 뛰었을 때 도달 가능한 모든 위치에 대해서 생각해 보자. k를 고정했으니까 점프 뛰는 순서를 바꿔서 \( 2^{k-1}, ..., 2, 1 \) 순서로 뛴다고 하면 결국 \( -2^k + 1 \) 과 \( 2^k - 1 \) 사이의 아무 홀수 위치에 다 도달 가능함을 알 수 있다. (머릿속으로 이진 트리를 그려 보자.)

따라서 X가 홀수이면  \( |X| \le 2^k - 1 \) 인 최소의 k가 답이 된다. X가 짝수이면, 0일 때만 답이 0이고(여기 유의!) 나머지는 -1이다.

B

맨 윗 행부터 한 행씩 맞추어 나간다고 하자. 맨 위 N-1개의 행을 제대로 맞추었다면, N번째 행도 맞추어졌다는 뜻이므로 N-1번만 반복하면 된다.

이번에 A번째 행을 맞출 차례, 즉 A번째 행에 N개의 A가 들어가도록 할 차례라고 하자. A행 위의 행들은 다 맞추어져 있으니 어떤 A가 A번째 줄에 없다면 무조건 아래에 있을 것이다. X행 Y열에 있는 A를 A행 B열로 (A행 위쪽에 맞춰놓은 것을 깨지 않으면서) 갖다놓고 싶다고 하면 다음과 같은 과정을 생각할 수 있다.

1. B=Y라면 X행을 1칸 옮긴다. (B와 Y를 다르게 만들기 위해) 
2. B열을 (A-X)칸 내린다.
3. X행 Y열에 있는 A가 X행 B열로 오도록 X행을 적절히 옮긴다.
4. B열을 다시 (A-X)칸 올린다.

A행 B열에 A가 들어있지 않은 모든 B에 대해 이 과정을 순차적으로 반복하면 A행을 A N개로 채울 수 있다. 연산 횟수 제한은 아주 넉넉하게 주어져 있으니 걱정할 필요 없다.

C

모든 빌딩의 옥상끼리 서로 볼 수 있도록 적절히 남겼다고 할 때, 남은 빌딩들이 어떤 조건을 만족해야 하는지 우선 살펴 보자. 여기서는 인접한 빌딩 옥상의 "기울기", 즉 (y좌표 차) / (x좌표 차) 가 중요한데, 어떤 인접한 세 빌딩 A, B, C에 대해 (A->B 기울기) > (B->C 기울기) 라면 A와 C가 서로 볼 수 없게 된다. 반대로, 임의의 인접한 세 A, B, C 빌딩에 대해 (A->B 기울기) <= (B->C 기울기) 를 만족한다면 모든 빌딩이 서로를 볼 수 있음도 쉽게 알 수 있다.

모든 빌딩 옥상끼리 서로 볼 수 있는 배치. 인접한 빌딩 간 기울기가 단조증가한다.

이제 DP[x][y] : (마지막으로 남긴 두 빌딩이 x번, y번 빌딩일 때 지금까지 최대로 남긴 빌딩 갯수) 로 정의하면 DP[x][y] = (z < x이고 (z->x 기울기) <= (x->y 기울기) 인 z들 중 DP[z][x]의 최댓값) + 1 이 됨을 알 수 있다. 높이가 엄청나게 높은 가상의 0번 빌딩이 있다고 가정하면 초기값 설정이 편하다. (DP[0][x] = 1로 설정하면 됨) 점화식을 그대로 계산하면 O(N^3)이라서 서브태스크 2까지 맞는다.

이것을 좀 더 빠르게 계산하려면, 위의 DP 계산에서 인접한 세 빌딩의 가운데에 해당하는 "x" 값을 고정해 보자. x<y인 임의의 y에 대해, DP[x][y]를 계산하는 데 필요한 DP값은 {DP[0][x], DP[1][x], ..., DP[x-1][x]} 로 모두 같으므로 이 DP값들을 (z->x 기울기) 순으로 정렬해 놓으면 각각의 DP[x][y]에 대해 max 값을 구해야 하는 범위가 구간 하나로 나타난다. 이분탐색이나 two pointer 기법 등을 사용하면 x 하나당 O(NlogN) 시간에 (정렬 포함) 모든 DP[x][y] (x<y)를 갱신할 수 있다. 이것을 구현하면 O(N^2logN)으로 전체 문제를 풀 수 있다.

D

세그먼트 트리로 분할정복 + 점 갱신 쿼리 문제를 풀 수 있다는 사실이 잘(?) 알려져 있다. (연습문제 추가예정) 몇 문제 풀어 봤다면 풀이는 금방 생각날 듯.

문제에서 주어지는 함수는 각각 x -> x + a 또는 x -> bx 꼴인데, 이는 f(x) = ax+b 꼴의 일차함수로 일반화할 수 있다. 이제 하고 싶은 일은 f(x) = ax+b 꼴의 함수 N개를 합성한 것을 빠르게 구하는 것이므로 세그먼트 트리의 각 노드에 "[l, r] 구간의 함수를 다 합성한 함수"를 저장하자. 리프 노드가 아닌 임의의 노드는 두 자식 노드의 합성인데, f(x) = ax+b, g(x)=cx+d라 할 때 g(f(x)) = (ca)x + (cb+d) 이므로 자식 노드의 (a, b) 값을 알고 있으면 부모 노드의 값 역시 바로 구할 수 있다.

어떤 점의 함수가 업데이트되면, 그 점을 포함하는 logN개의 노드만 합성한 함수를 새로 업데이트하면 된다. 이제 답은 [1, N] 구간을 다 합성한 함수가 F라고 할 때 F(0)이므로 쿼리당 O(logN)에 구할 수 있다. 

E

조형물 둘레에서 햇빛이 비치는 부분의 총 길이를 구한다고 해 보자. 해의 입장에서 조형물을 바라본다고 할 때, 해는 조형물이 하나의 직선처럼 보일 것이다.

아래 그림을 보자. 햇빛은 각 x-y 값에 대해 딱 한 점에만 비치므로, 결국 (x좌표 - y좌표) 값의 범위, 즉 x-y의 "최댓값 - 최솟값" 이 바로 햇빛이 조형물에 비치는 총 길이임을 알 수 있다!

조형물에서 햇빛이 비치는 선들을 잘 옮겨 보면 전체 조형물이 이루는 (x-y) 값의 범위에 딱 맞게 할 수 있다.

조형물에 생기는 그늘의 길이는 (조형물 총 둘레) - (햇빛의 길이) 이고, 조형물 양 옆의 땅에 생기는 그늘의 길이는 아까와 유사하게 (x-y) 값의 최댓값/최솟값과 조형물의 시작점/끝점의 거리로 구할 수 있다.

어렵게 생각하면 얼마든지 어려워질 수 있는 문제. 아이디어가 꽤 재미있다.

F

대회 중에는 Subtask 1까지밖에 못 풀었다. 풀이를 들으면 상당히 허탈해지는 문제이다..

명령어의 수를 줄이기 위해서는 Start와 End가 꼭 필요한데, 한 번씩밖에 못 쓰기 때문에 참 어렵다. 접근의 핵심은 다음 형태의 압축 과정을 생각하는 것이다.

1. 메모리 셀 하나의 값으로 임의의 k비트 Binary String을 출력할 수 있도록 전처리한다.
2. Write 명령을 (n/k)번 사용하여 출력할 문자열의 각 k비트에 해당하는 값을 순차적으로 입력해 둔다.
3. Start - End 절을 사용해 출력을 수행한다. 출력 명령어는 Counter의 값을 계속 1씩 증가시키면서 각각의 Counter 자리에 들어있는 메모리 값(2에서 넣은)을 가지고 1을 활용해 k비트씩 출력한다.

임의의 k비트 Binary String을 출력하는 방법은 높이가 k인 완전이진트리를 1~(2^k-1) 번 메모리 셀에 만들어 놓은 다음 적절한 노드 x부터 출발하여 "Print **...*x"(별이 k개), ..., "Print **x", "Print *x" 를 순서대로 수행하는 것이다. (실제 구현 시에는 x의 값이 또 어떤 메모리 셀에 들어있을 것이므로 별을 더 붙여야 될 수 있으니 유의)

사용하는 총 명령어가 대충 2^k + n/k 개이므로, k를 7~8 정도로 설정해 주면 2000번 안에 가능하다.

G

열심히 생각을 하면 O(N^3) 풀이를 얻어낼 수 있는데, 정해는 그 풀이와 전혀 딴 판이라고 한다.

아직 풀이 슬라이드를 제대로 못 읽었는데, 읽고 나서 추가할 예정.

H

P는 "최대 K 제한"의 의미일 뿐이라는 점을 일단 파악해야 한다. 즉, 그냥 경우의 수가 정확히 K인 격자판을 만든다고 생각하자.

보통 이런 식으로 "정확히 K개"를 만드는 형태의 Constructive 문제는 이진수 표현을 통한 접근이 유용하게 먹힌다. 즉, 답이 \( 2^m \) 꼴인 경우를 먼저 만든 뒤 실제 주어진 K의 이진수 표현에 따라 적절히 합쳐주는 형식이다.

우선, 경우의 수가 2배씩 늘어나도록 하는 격자를 아래 그림과 같이 설계할 수 있다.

이제, K의 이진수 표현에서 1이 켜진 각 비트에 대해 해당하는 \( 2^m \) 을 답에 합쳐주면 된다. 이는 맨 아래로 길을 하나 뚫어주는 방식으로 구현 가능하다. 예를 들어, K = 7인 경우 아래와 같이 해 주면 된다.

K의 범위가 \( 2^{30} \) 이하이므로, \( 2^m \) 꼴을 만드는 격자가 대충 30x60 크기로 필요하다. 밑에 길을 뚫으려면 행을 3개 정도 밑에 추가하면 되니 33x60 정도의 격자면 문제를 푸는 데 충분하다.