서론
본선 떨어지면 창피할까 봐 1차 예선 후기도 안 올렸는데, 다행히 본선 진출할 것 같아서 1/2차 후기를 함께 올립니다.
점수는 다음과 같습니다.
번호 | 1차 예선 | 점수 | 2차 예선 | 점수 |
---|---|---|---|---|
1 | 친구들 | 80/80 | 원 안의 점 | 100/100 |
2 | 이진수 | 150/150 | 직8각형 | 200/200 |
3 | No Cycle | 180/180 | 산탄총 | 300/300 |
4 | 예약 시스템 | 88/190 | 패턴 매칭 | 209/400 |
5 | 차이 | 200/200 | Hanoi Tower | 33/500 |
총합 | 698/800 | 842/1500 |
데스크탑에서 보시는 분들은 오른쪽 사이드바를 활용하시면 원하는 문제로 쉽게 이동하실 수 있습니다.
1차 예선
1차 예선답게 쉬운 문제들이 출제되었습니다. 1235 풀고 4번 제출했는데 88점 밖에 안 나오길래 디버깅하기 귀찮아서 던지고 자러갔습니다.
1. 친구들
$i$와 $i+D_i$를 연결하고 컴포넌트의 개수를 세면 됩니다.
1 |
|
2. 이진수
??? : Lexicographical 2-SAT
문제를 보자마자 Lexicographical 2-SAT을 검색해봤지만 아무것도 얻지 못했습니다.
정답은 “무조건 0 / 무조건 1인 위치”를 먼저 처리한 뒤, 앞에서부터 최대한 0을 많이 배치하는 그리디 알고리즘을 이용해 구할 수 있습니다.
만약 $A_i = 0$이라면 $B_{i-T}$와 $B_{i+T}$는 0이 되어야 합니다. 또한, $i \leq K$이거나 $i \geq N-K$이면 $B_i$에 관여하는 $A$의 값이 1개 이하이므로 값을 결정할 수 있습니다. 이렇게 답을 고정하고 나면 답이 고정되지 않은 위치가 남아있을텐데, 해당 위치에는 1이 와도 상관 없다는 것을 알 수 있습니다.
이제, 앞에서부터 최대한 0을 많이 배치하는 그리디 알고리즘을 수행합니다. 구체적으로, 앞에서부터 “아직 확정이 안 된 위치”를 차례대로 순회하면서, 해당 위치에 0을 넣어도 올바른 비트열을 만들 수 있는지 확인하면 됩니다.
1 |
|
3. No Cycle
??? : Reachability Problem
방향 간선으로만 위상 정렬을 한 뒤, $v$에서 $u$로 가는 경로가 없다면(간선 $(u,v)$를 추가해도 사이클이 안 생기면) $0$, $v$에서 $u$로 가는 경로가 있다면 $1$을 출력하면 됩니다. AMPPZ의 모 문제가 생각나서 Reachability Problem를 검색했지만 2번과 마찬가지로 아무것도 얻지 못했습니다.
사실 입력 범위가 작아서 매번 경로가 존재하고 간선을 넣어도 됩니다.
1 |
|
4. 예약 시스템 (X)
5번을 풀어서 4번은 대충 긁고 다시 자러갔습니다.
5. 차이
BOJ 3830 교수님은 기다리지 않는다와 똑같은 문제입니다. (풀이)
위 링크에 나와있는 것처럼 Union-Find로 풀면 되지만, 2년 전보다 실력이 감소했는지 도저히 이쁘게 구현할 방법이 떠오르지 않아 Heavy Light Decomposition을 들고 와서 밀었습니다.
사실 Link Cut Tree 짜다가 중간에 멈춘 거라서, 이정도면 양호하다고 생각합니다.
1 |
|
2차 예선
미친듯이 말렸습니다. 1번은 풀어본 문제라서 빨리 풀었고 2번도 운좋게 전체 20번째로 풀긴 했지만, 그 다음부터 엄청 말렸습니다.
3번 문제 Subtask 1/2를 긁기 위한 코드를 7번이나 제출했지만 모두 0점을 받아서 멘탈이 심하게 흔들렸습니다. 이러다 300점으로 마무리하겠다는 생각이 들어서 4번을 먼저 풀었습니다.
처음에는 4번에서 쓸데 없는 log를 붙여서 81점만 받았습니다. 이 당시에는 시간 복잡도를 정확하게 계산하지 않아서 단순히 제 풀이가 느린 풀이라고 생각하고 넘어갔습니다.
다시 3번으로 돌아와서, 코드를 전부 밀고 처음부터 다시 짰습니다. 2차원 펜윅 트리를 이용한 $O(N^2K \log^2 N)$ 풀이를 제출해서 47점을 받았습니다. 코드를 잠시 살펴보니 펜윅 트리 대신 누적합 배열을 써도 충분하다는 것을 깨닫고 $O(N^2K)$ 풀이를 제출해서 107점을 추가로 받았습니다.
3번에서 log^2를 떼고 나니 4번 풀이에 붙은 쓸데 없는 log가 생각나서 없애고 128점을 추가로 받았습니다. 이때가 대회 종료 4시간 전입니다.
제출 기회가 한 번 밖에 남지 않은 3번 문제와 건들지도 않은 5번 문제 중 어떤 것을 잡을지 고민했고, 먼저 완전탐색으로 빠르게 5번을 긁기로 결정했습니다. 대충 $O(3^N)$짜리 BFS를 구현해서 $N = 18$인 문제를 해결해 33점을 받았습니다.
3번 문제 풀이가 떠오르지 않아서 침대에 누워있었는데, 대회 종료 80분 전에 갑자기 풀이가 떠올라서 구현을 시작했습니다. 인덱스 실수가 수십 번 발생했고, 4번 정도 갈아엎어서 예제가 나오는 코드를 완성한 것이 대회 종료 5분 전이었습니다. 로컬에서 돌려보니 8초 걸려서(TL은 3초) 최적화를 시도했지만 7초까지 밖에 줄이지 못했습니다.
대회 종료 1분 전에 FastIO를 사용할까 고민했지만, 5년 전 모종의 사건 때문에 혹시 몰라서 사용하지 않기로 결정했습니다. 결국 로컬에서 7초 걸리는 코드를 대회 종료 30초 전에 제출했고, 다행히 AC를 받으면서 한숨을 돌렸습니다.
하루를 온전히 PS에 투자하는 경험은 약 1년 만에 해봤는데, 정말 즐거웠습니다.
문제 난이도는 1번 G? / 2번 P5 / 3번 P1-D5 / 4번 Subtask2 D5 / 4번 D3으로 예상합니다.
1. 원 안의 점
Atcoder ABC-D에 나와서 많은 이들을 고통스럽게 했던 ABC191-D Circle Lattice Points의 하위 호환입니다.
$Y$축 기준으로 반으로 자른 뒤, 각 $X$좌표마다 가능한 $Y$좌표의 최대/최소값을 투포인터 느낌으로 관리하면 $O(R)$에 문제를 풀 수 있습니다. 자세한 방식은 코드를 참고해주세요.
1 |
|
2. 직8각형
점이 8개니까 $8!=40\,320$개의 순열을 모두 보면서, 각 점이 직8각형의 꼭짓점이 되는 모든 경우를 고려해도 됩니다. 또한, $L_1$거리를 사용하기 때문에 $X$, $Y$좌표를 독립적으로 생각할 수 있습니다.
$p_0$의 위치를 $(X_0, Y_0)$이라고 정의합시다. $p_1, \cdots, p_7$의 위치는 각각 $(X_0, Y_0+K)$, $(X_0+K, Y_0+2K)$, $(X_0+2K, Y_0+2K)$, $(X_0+3K, Y_0+K)$, $(X_0+3K, Y_0)$, $(X_0+2K, Y_0-K)$, $(X_0+K, Y_0-K)$입니다.
두 배열 $dx[] = \left{ 0,0,1,2,3,3,2,1 \right}$, $dy[] = \left{ 0,1,2,2,1,0,-1,-1 \right}$을 정의하면, $p_i = (X_0 + dx[i]\cdot K, Y_0 + dy[i]\cdot K)$로 표현할 수 있습니다.
점 $(x_i, y_i)$를 $p_i$와 매칭시키는 비용은 $\vert x_i - X_0 - dx[i]\cdot K \vert + \vert y_i - Y_0 - dy[i]\cdot K \vert$입니다. 즉, $\sum_i \vert x_i - X_0 - dx[i] \cdot K \vert$와 $\sum_i \vert y_i - Y_0 - dy[i]\cdot K$를 최소화하는 $X_0, Y_0$을 찾아야 합니다. 그러한 $X_0, Y_0$은 절댓값 기호 안에 있는 식을 0으로 만드는 값들의 중앙값($x_i-dx[i]\cdot K$, $y_i-dy[i]\cdot K$의 중앙값)이라는 것이 잘 알려져 있으므로 적절한 방법을 이용해 중앙값을 찾으면 됩니다. 저는 std::nth_element
를 이용했습니다.
시간 제한 관련해서 이슈가 있었던 것으로 아는데, 저는 별 문제 없었습니다
1 |
|
3. 산탄총
Subtask2 풀이($O(N^2K)$)풀이부터 알아봅시다.
다이아몬드 격자는 45도 회전하는 것이 좋습니다. $(i, j)$를 $(i-j, i+j)$로 바꾸면 됩니다. $A_{i,j}$가 영향을 주는 위치는 아래 그림처럼 나타낼 수 있습니다. 오른쪽의 회색 격자는 실제로 사용하지 않는 칸이므로 신경쓰지 않아도 됩니다.
45도 회전시킨 오른쪽 그림을 보면, 직사각형 영역에 1을 더하는 것을 $K$번 더한 결과와 동일하다는 것을 알 수 있습니다. 그러므로 $O(N^2)$개의 모든 칸에 대해 $O(K)$개의 직사각형 영역을 1 증가시키는 작업을 2D Prefix Sum을 이용해 수행하면 $O(N^2K)$에 문제를 풀어 154점을 얻을 수 있습니다.
1 |
|
이 풀이를 열심히 최적화하면 $O(N^2)$ 풀이를 얻을 수 있습니다.
2D Prefix Sum을 구하기 위해 2차원 배열에 더하는 값은 아래 그림처럼 나타낼 수 있습니다.
어? 굉장히 익숙한 그림입니다. 대각선 구간에 하나씩 더하는 대신, 대각선에 대한 누적합도 같이 관리하면 됩니다!
수행할 작업들 간의 관계가 상당히 복잡합니다. 정리하자면,
- 대각선 방향의 누적합을 관리하기 위해 $O(N^2)$개의 포인트에 덧셈을 하고 누적합을 $O(N^2)$ 시간에 구합니다.
- (1)에서 구한 값을 이용해 Subtask2에서 관리하는 2D Prefix Sum을 $O(N^2)$시간에 구합니다.
- (2)에서 2D Prefix Sum을 이용해 실제 최댓값을 구합니다.
전체 문제를 $O(N^2)$시간에 풀 수 있습니다.
1 |
|
4. 패턴 매칭 (Subtask 2 풀이)
??? : 어 이거 XXX 문제인데?
Subtask2와 똑같은 문제가 제가 참가했던 TST에 나왔다는 얘기가 있던데, 저는 본 기억이 없습니다. 아마 문자열 문제라는 것을 보자마자 넘기지 않았나 싶습니다. 1년 반이 지난 지금은 잘 풀었으니 성장했다고 봐도 되겠죠?
제 주변의 몇몇 분들은 TST를 통해 KMP의 아이디어를 생각한 것 같은데, 저는 CEOI 2015 Matching / 2020 서강대 파인애플 피자를 풀었던 기억을 통해서 KMP를 떠올렸습니다.
KMP와 똑같이, 패턴의 Failure Function을 구한 다음 원본 문자열과 패턴을 비교하는 방식으로 진행합니다. 문자열 $A, B$가 동치일 때 $A+a$와 $B+b$가 동치인지 확인하는 로직을 효율적으로 구현해야 합니다. Failure Function부터 구해봅시다.
1 |
|
일반적인 KMP에서 Failure Function을 구하는 함수는 다음과 같이 작성할 수 있습니다.
1 |
|
여기에서 P[i] == P[j]
는 P[i-j..i]
와 P[0..j]
가 동치인지, 즉 P[i-j..i] = P[0..j]
인지 확인하는 부분입니다. 이 부분을 Match(i, j)
라는 함수로 나타낸 뒤, Match
함수를 잘 작성하는 것을 목표로 할 것입니다.
1 |
|
만약 P[i-j..i-1]
에 이미 P[i]
가 등장했다면 P[i]
는 매칭되어야 하는 짝이 정해져 있습니다. 마찬가지로, P[0..j-1]
에 이미 P[j]
가 등장했다면 P[j]
는 매칭되어야 하는 짝이 정해져 있습니다. 등장한 적이 없다면 아직 매칭된 적 없는 임의의 문자와 매칭해도 됩니다.
이 정보를 빠르게 처리하는 방법으로, 각 문자 P[x]
마다 자신과 똑같은 문자가 등장하는 가장 최근의 위치 prv[x]
를 저장합니다. prv[x]
를 알고 있다면, prv[i] ≥ i-j, prv[j] != NULL
등을 확인해서 매칭 여부를 상수 시간에 확인할 수 있습니다. 이때, prv
배열을 구하는 것은 $O(\vert P \vert)$ 시간에 할 수 있습니다.
이렇게 작성한 GetFail
함수는 다음과 같습니다.
1 |
|
일반적인 KMP에서 실제 매칭을 수행하는 코드는 다음과 같이 작성할 수 있습니다.
1 |
|
Failure Function을 구하는 코드와 매우 유사합니다. S[i] == P[j]
를 비교하는 것은 S[j-i..i] = P[0..j]
를 비교하는 것입니다. Failure Function을 구할 때 했던 것처럼, prv
배열을 관리하면 매칭을 잘 수행할 수 있습니다.
1 |
|
5. Hanoi Tower (33~44점 풀이)
BFS를 돌리면 $N = 18$일 때의 정답(33점)은 쉽게 구할 수 있습니다. BFS 돌려놓고 밥 먹고 오면 $N = 19$일 때의 답(44점)도 얻을 수 있습니다. 근데 codeground에 코드 길이 제한이 있어서 $N=19$는 제출하지 못했습니다.
1 |
|