* 이 글에서는 대회 후기+복기 위주로 작성하고, 어려운 문제는 따로 글로 작성할 예정이다.
경기과학고 ps 동아리 나코더에서 12월 27일 송년대회가 열렸는데, 나는 [BIG SHOT]이라는 팀 이름으로 같은 39기인 박종경, 김기범과 함께 참가했다.
5시간동안 12문제를 풀어야 했고, A, B, E, I, J, K를 풀고 2등과 근소한 차이(패널티 40차이)로 3등을 했다.
0:00 ~ 0:13
내가 ABCD, 기범이가 EFGH, 종경이가 IJKL을 읽었다. A에 넥슨 그림이 있어서 넥슨 스폰서 문제임을 알게 되었고, 특별상이 걸린 넥슨 스폰서 문제면 어려운 문제는 아닐 것으로 추측하고 바로 풀었다. 오타내고 1번 틀려서 2번만에 맞았다.(0:13:19)
A는 두 수열 $A_i$와 $B_i$가 주어지는데, $A_i + B_i$의 합이 $X$로 일정하다. 수열에서 $K$개의 $i$를 선택하여 선택한 $A$합과 $B$합의 곱을 최대화해야 하는 문제이다.
제한이 작아서 임의의 $K$개의 $A$ 합으로 가능한 수의 종류가 16000개 정도 이하이고, $N$도 80보다 작아서 dp를 사용하면 풀 수 있다.
0:14 ~ 0:34
옆 팀에서 I가 풀렸고, 종경이가 쉬운 문제임을 알아채고 바로 풀었다. 한 번에 맞추었다.
I 문제는 트리가 특이한 방식으로 주어지고, $[l_i, r_i]$ 시간에 트리 두 정점 사이 경로에 정수를 더하는 연산이 $Q$개 주어지고, 최종 정점에 쓰인 숫자를 구하는 문제이다. ETT와 세그를 잘 쓰면 쉽게 풀린다.
0:35 ~ 0:54
내가 B Li Chao Tree 풀이를 찾았는데, 내가 짤 줄 몰라서 종경이한테 넘겼다. 종경이가 더 쉬운 풀이를 찾고 구현하기 시작했다. 그 동안 기범이가 E 풀이를 찾고 구현했는데, 2번 틀리고 맞았다.
0:55 ~ 2:14
그 시간 이후로 스코어보드는 4솔 이상이 계속 안 나오다가, 내가 K 풀이를 찾았다. 그때쯤 종경이는 Li Chao Tree를 안 쓰는 풀이를 찾고 풀어서 2번만에 맞았다.
B는 $A_i$와 $B_i$가 주어지고, $k$라는 상수가 주어진다. 1이상 $M$이하의 모든 정수 $x$에 대해, $(B_i - kx)/(A_i + kx)$의 최댓값을 구해야 한다. 특정 $x$에 대해 답이 $a$ 이상인지 물어보는 질문은, $(B_i -kx)\ge (A_i+kx)a$로 바꿀 수 있고, 식을 변형하여 풀 수 있다는 것 같다. 자세한 풀이는 듣지 못했다.
2:15 ~ 2:41
K풀이를 찾고 구현해서 맞았다. 문제 조건을 약간 잘 못 읽어서 1번 틀렸다. 여기서 한번 안 틀리고 A에서 한번 안 틀리면 2등이다.
K는 가중치 있는 트리에서 복잡한 연산이 주어지고, 이를 빠르게 처리해야 한다. 문제 요약은 생략한다.
우선 센트로이드 트리를 만들고, 적절한 자료구조를 통해 2번 쿼리가 주어졌을 때 왕이 어느 순서로 이동하는지 구해준다. 다음으로, 각 정점마다 그 정점의 센트로이드 트리의 서브트리에 대해 트리디피를 해 줄 것이다. 트리디피의 경우, 루트로부터 이동하는 최단 비용을 구해줄 것인데, 이는 dfs를 돌면서 cht를 활용하면 $O(Nlog_2{N})$에 처리할 수 있다. 또한 tp가 1인 경우와 2인 경우의 비용 차이는, 국왕이 $v$에 있고 $u$로 이동한다 할 때 $C_u - C_v$정도 차이가 난다. 따라서 tp가 2인 경우도 바로 구할 수 있다. 각 정점이 트리디피에 사용되는 횟수는 센트로이드 트리 상의 조상의 수와 같고, 센트로이드 트리의 특징상 깊이가 $O(log_2{N})$이다. 따라서 전체 시간복잡도 $O(Nlog_2^2{N})$에 풀린다.
2:42 ~ 4:20
꽤 오랜 시간동안 문제가 안 풀렸다. 처음에는 내가 C를 잡고, 종경이와 기범이가 J를 잡았는데, 둘 다 풀렸다. 그런데 C에서 Li-Chao Tree가 필요해서 J 구현을 기범이에게, C 구현을 종경이에게 맡겼다. 이때 4시간 지났었던 것 같다. C는 Li-Chao Tree를 사용하면 $O(KNlog_2{N})$에, CHT를 사용하면 $O(KNlog_2^2{N})$에 풀리는데, 제한을 보니 CHT를 쓰면 2.4억에 1초로 tle가 날 것 같아서 풀이를 버렸다. 오늘 들어 보니 CHT도 돈다는 것 같은데, 아마 CHT의 교점을 찾는 이분탐색의 시간 복잡도가 충분히 작아서일 것이다. L을 풀던 중, 종경이가 dp식을 짜 달라고 해서 자리를 바꾸었다. 그때쯤 J에 기범이가 첫 제출을 했고, rte가 났다.
4:21 ~ 4:42
기범이가 rte 원인을 찾았는데, 고치니까 WA가 떴다. 이때쯤 나도 C 코딩을 거의 끝냈다.
4:43 ~ 4:50
C를 제출했고 틀렸다. 난 C를 디버깅하고, 종경이와 기범이가 J의 반례를 열심히 찾았고, s와 t를 바꿔 썼다는 사실을 발견하게 되었다. 고치니까 바로 맞았다. 대회 끝나고 들어 보니까 CHT는 실수를 쓰면 오차때문에 터지고, 정수를 쓰면 int128을 써야 오버플로우가 안 난다고 한다. 정해는 dnc opt라고 한다.
4:51 ~ 5:00
C를 디버깅하려 했으나 실패했다. 코드에는 특별히 틀린 부분이 없는 것 같았으나, 낮은 확률로 Li-Chao Tree 구현이 틀렸거나, 중간 계산 과정에서 long long 범위를 넘어가서 틀렸을 것으로 보고 있다. 자세한건 오픈 컨테스트 이후 제출해봐야 알 것 같다.
대회 이후
F, L이 예상한 것 보다 더 많이 쉽다는 사실을 알게 되었다. 특히 F는 풀이에 거의 근접했으나, 마지막 아이디어가 부족해서 풀지 못 했다. 곧 스코어보드 오프닝이 있었고, 안정적으로 3등을 하여 마우스를 받았다.
