Good Bye, BOJ 2022! 후기 + 풀이

2022년 12월 31일에 열린 Good Bye, BOJ 2022! 대회에 참가하였다. 7솔브로 13등을 기록하였다.

PS 판의 수준이 얼마나 높아졌는지를 뼈저리게 느낄 수 있는 시간이었다. 사람들이 문제를 너무 잘 푼다..

그리고 최근 들어 갑자기 문제 풀이를 내는 데 걸리는 시간이 급격히 길어진 느낌인데, 해결할 방법을 모르겠다. 시간 지나면 나아지려나..

대회 타임라인

A는 적당히 무난하게 빨리 풀 수 있었다. 파이썬을 쓰고 싶을 정도로 쉽지는 않은 문제라서 오히려 틀리지 않을 수 있었다.

B를 봤는데 벌써부터 별로 안 쉬워서 약간 슬펐다. 처음에 파라메트릭으로 접근했다가 다행히 다 짜기 전에 이상함을 깨달았다. 그리고 풀이를 대충 생각한 다음 긴가민가 하면서 냈는데 다행히 한 번에 맞을 수 있었다.

C는 어디서 본 거 같이 생긴 문제였고, 똑같이 풀면 되는 문제였다. 그런데 처음에 짠 코드가 예제는 다 맞는데 틀렸다. 왜 틀린지 한참을 보다가 전혀 모르겠어서 그냥 밀고 다시 짰더니 맞았다. 여기서부터 살짝 뭔가 꼬인 것 같다.

D는 한 10분 동안 생각을 계속 했는데 전혀 모르겠어서 한 번 더 슬퍼졌다. 문제를 다시 읽어 보니 초기 격자에 있는 수들이 모두 X보다 작다는 조건이 절묘하게 숨어 있었다. 다시 읽은 다음에는 풀이를 찾을 수 있었고, 코딩을 좀 드럽게 해서 틀릴 거 같았는데 다행히 그러진 않았다.

이제 E랑 F랑 G를 쭉 읽었는데 전혀 생각이 나질 않았다. E랑 F는 풀이의 초입부터 어디 있는지 전혀 찾을 수가 없었고, G는 머릿속 기억을 끄집어내 구글링을 좀 하니까 뭔가 나오긴 했는데 "간선 추가 순서"를 고려하는 것을 어떻게 하는 건지 도통 알 수가 없었다.

그렇게 한참을 고민하다가 E 풀이가 어떻게 생겼는지 가닥을 잡았고, 디테일을 완성하는 데 생각보다 시간이 걸리긴 했지만 어쨌든 짜서 냈다. 다행히 한 번만 틀리고 맞았다.

그리고 나서 F를 보니 드디어 식을 올바르게 가지고 노는 법을 깨달을 수 있었고, 얘는 디테일이 E보다 훨씬 간단해서 바로 후루룩 짜서 맞았다.

이제 G랑 H가 남았는데, 이미 누적된 정신적 데미지가 너무 커서 그런지 G는 더 이상 뭔가를 할 수가 없었다. 그래서 H를 잡기로 했고, CHT 쪽으로 생각을 하니 풀이를 나름 빠르게 찾을 수 있었다. 풀이에 필요한 자료구조를 예전에 백준 문제 풀다가 짰었다는 사실을 기억해내고, 심지어 문제 제목까지 기억해내는 데 성공하여 코딩 시간을 크게 절약할 수 있었다. (그거 복붙 안해오고 직접 짰으면 시간 내에 못풀었을 듯) 코드의 나머지 절반을 완성하는 데 시간을 좀 더 쓰니 30분이 남은 시점에 첫 제출을 할 수 있었다.
그런데 틀려서, 더 늦기 전에 naive를 짜고 (naive가 매우 쉬운 문제라 다행..) 비교해보는 코드를 짜서 디버깅을 시도했다. 두 번의 오류 수정을 거친 끝에 대회 끝나기 10분 전에 AC를 띄울 수 있었다.

G는 10분 안에는 딱 봐도 못 짜는 문제였기 때문에 바로 침대로 도망갔다.

복기

C에서부터 시원하게 맞왜틀 한번 갈겨주고 시작한 게 원흉이었는지 모르겠는데, D,E,F 모두 생각보다 훨씬 오래 난항을 겪었다. E랑 F는 올바른 풀이의 첫 단추를 끼우고 나서부터는 금방 풀고 짜고 했는데, 그 첫 단추를 찾는 게 너무 오래 걸렸다. 연습 부족인가 라고 하기엔 최근 몇 달 동안 연습을 너무 많이 한 거 같은데.. 

G가 하도 안 풀리길래 결국 H를 잡았는데, 그래도 풀이가 금방 떠오름 + 필요한 자료구조를 내가 예전에 짜둔 적이 있음 등이 겹쳐 다행히도 대회 끝나기 전에 맞을 수 있었다. 그 와중에 너무 오랜만에 짜보는 자료구조라서 + 예외 처리가 은근 있어서 디버깅이 꽤 걸리긴 했다.

G는 끝나고 나서 보니 간선 추가 순서를 고려하는 부분이 매우 trivial했다. 그런데 왜인지 모르게 대회 중에는 전혀 그렇지 않다고 생각했다.. 오늘 대회 중 가장 아쉬운 부분.

문제별 풀이

A

1부터 5000까지 각 수의 진약수의 합을 미리 구해놓자. 이제 주어지는 각각의 n마다 문제에서 물어보는 조건을 그대로 검사해 주면 O(n^2+Tn) 내지는 O(nlogn+Tn)에 해결할 수 있다. A번이라 그런지 제한이 나름 널널해서 대충대충 하면 되는 듯.

B

묶음의 개수 K를 결정했다고 하자. K>=3일 때, 최적의 partition은 반드시 "가장 큰 K-1개는 단독으로 남기고 나머지들을 합친 것"이다. 그렇게 했을 때 점수가 "(floor(K/2)+1)번째로 큰 수" 인데, 큰 수들을 괜히 합쳐 버리면 점수가 저것보다 높아질 수가 없기 때문이다.

그런데 방금 한 말을 잘 살펴 보면 K>4일 때는 고려할 필요가 없음을 알 수 있다. 즉, K>=3일 경우의 가능한 최대 점수는 "2번째로 큰 수"이다.

K=1일 경우 점수는 "전체 평균"이고, K=2일 경우는 생각을 해 보면 K=1보다 좋을 수가 없음을 알 수 있다.

이제 답은 max(전체 평균, 2번째로 큰 수) 이다. N=1일 때는 예외 처리.

C

https://www.acmicpc.net/problem/5914 얘랑 거의 똑같은 문제다.

핵심 관찰은, 임의의 두 수에 대해 그 둘의 앞/뒤 순서가 바뀌어 있는 데이터는 많아야 하나라는 것이다. (원래 a가 b 앞에 있었다고 하면, b를 들고 a 앞으로 옮겨야지만 둘의 순서가 바뀜.)

따라서, 임의의 두 수를 주면 둘 중 어느 게 앞에 있어야 하는지를 알 수 있다. 세 개의 데이터에서 두 수의 위치를 각각 찾아 앞에 있는 경우가 더 많은 쪽이 원래 앞에 있었던 것이다.

이제 이것을 비교 함수로 하여 std::sort에 때려 넣으면 정답이 튀어나온다. 각 수가 각 데이터에서 몇 번째인지를 전처리해 놓으면 비교 함수가 O(1)에 작동하니 시간 복잡도는 O(nlogn).

D

답에 대한 이분 탐색을 굉장히 하고 싶게 생긴 문제 세팅이다. 결정 문제로 바꾸어 보면, "보정을 K번 이하로 하여 인접한 cell의 값 차이를 모두 d 이하로 만들 수 있는가?"이다.

우선 현재 상황에서 d 초과로 차이가 나는 두 cell이 있으면 둘 중 하나는 건드려야 하는데, 보정 후의 값 X가 현재 격자상의 수보다 항상 크거나 같은 값이기 때문에 다음 사실이 성립한다 : "일단 둘 중에 작은 cell을 X로 바꾼 다음에 생각해도 좋다". 둘 중에 큰 쪽을 건드리면 차이가 늘면 늘지 줄지는 않기 때문이고, 어쨌든 결국 둘 중 하나는 바꾸어야 하기 때문이다. 이 과정을 더 이상 보정할 필요가 없어질 때까지 계속 하면 될 것이다.

이제 처음 상황에서 보정을 해야 할 cell들을 찾은 뒤에, BFS를 수행하여 더 이상 건드릴 필요가 없어질 때까지 계속 보정을 수행하면 된다. 어떤 cell을 X로 바꾸었을 때, 인접한 cell들 중 값이 X-d 미만인 것이 있으면 걔도 보정을 해야만 하니 queue에 추가해주는 식이다.

이렇게 하면 결정 문제를 O(NM) 시간에 풀 수 있으니, 전체 시간 복잡도는 O(NMlogX).

E

우선, 편의상 a >= c라고 가정하자. a < c면 승<->패를 바꾸어 생각하면 된다.
그리고 최댓값을 구하는 것만 설명하겠다. 최솟값은 상황이 대칭적이라 잘 생각해서 비슷하게 처리하면 된다.

"k등의 점수로 가능한 최댓값이 X"라는 것은, 결국 "상위 k명의 점수가 모두 X 이상"일 수 있는 최대의 X를 구하는 것이다. 우선 핵심적인 관찰은 상위 k명이 치른 경기를 "하위 n-k명이랑 치른 경기 + 상위 k명간의 리그전"으로 분리하는 것이다.

일단 생각을 해 보면, 하위 n-k명이랑 치른 경기 결과는 아무렇게나 골라도 된다! 우리 입맛대로 고를 수 있으니, 그냥 a랑 b 중에 더 큰 걸로 꽉 채우면 된다.

이제 상위 k명 간의 리그전에 대해 생각을 해야 되는데, 우리가 주목하는 것은 k등의 점수이니 "꼴찌의 점수로 가능한 최댓값"을 구하는 것으로 문제가 바뀐다. 이것은 역시 생각을 해 보면 무승부의 개수에 따라 다음의 k가지 결과 중 하나만 고려해도 됨을 알 수 있다.

(k-1)무 / (k-2)무 1패 / (k-3)무 1승 1패 / (k-4)무 1승 2패 / ... / floor((k-1)/2)승 floor(k/2)패

무승부가 하나 줄어들 때마다 패/승/패/승.. 이 번갈아가면서 하나씩 추가되는 형태이다. 이제 여기서 최댓값을 찾아야 되는데, 2개 단위로 묶어서 보았을 때 delta가 일정하기 때문에 홀/짝으로 나누면 각각이 일차함수가 되고, 결국 양쪽 끝 2개만 보아도 최댓값을 항상 찾을 수 있다.

F

위치 X에서 출발하여 위치 0까지 도달하는 데 걸리는 시간에 주목하자.

위 그림에서 보듯이, 결국 걸리는 총 시간을 (정수)/MV 꼴로 나타낼 수 있다. 이제 각 물건을 집기로 했을 때 총 시간에 기여하는 양을 생각해 보면, 위치 x이고 질량 m일 때 총 시간의 분자에 mx만큼 기여하며, 이는 다른 물건과 완전히 독립적임을 알 수 있다.

따라서 각 물건을 비용 mx, 가치 c라고 두면 주어진 budget 안에서 가치 합이 최대가 되도록 물건을 구매하는 가장 기본적인 knapsack 문제로 환원된다! 총 Budget은 문제 조건에 따라 잘 생각해 보면 M(VT-X) 임을 알 수 있으니, 이 값이 0 미만이면 -1을 출력하고 아니라면 앞서 말한 knapsack 문제의 답을 출력하면 된다. 시간복잡도는 단순 DP를 하면 O(NMVT)인데, 1억이라 약간 불안하다고 생각할 수 있으나 공간복잡도 O(MVT)로 구현하면 알고리즘이 매우 단순한 관계로 넉넉하게 잘 나온다.

G

간선 추가 순서를 고려하지 않는 버전의 문제는 매우 잘 알려져 있다. 심지어 SCPC 1회 본선에도 나왔었다. codeground에 가서 한 번 찾아보자.

Kruskal's Algorithm의 작동 과정을 간선 가중치별로 묶어서 살펴 보자. 특정 가중치의 간선들을 고려할 때, 그것보다 낮은 가중치 간선들로 이어진 정점들은 하나로 묶을 수 있다.
이제 이렇게 정점을 묶은 새로운 그래프에서 특정 가중치 간선들을 고려하면 component 여러 개로 이루어져 있을 텐데, component마다 해당 컴포넌트에서 만들 수 있는 spanning tree의 개수를 구하고 그것을 모두 곱하면 답이 됨을 알 수 있다.
그래프에서 spanning tree의 개수를 구하는 것이 문제인데, 이는 구글에 counting number of spanning trees 등의 키워드로 검색하면 방법을 금방 찾을 수 있다. (Kirchhoff's theorem)

간선 추가 순서를 고려하는 것은 매우 간단한데, 매번 새로 만들어지는 spanning tree마다 (간선 개수)! 만큼을 곱하면 끝이다. 사실상 똑같은 문제라고 보면 될듯 하다.

H

k가 정해져 있다고 할 때, [k, n]에 속하는 각각의 j에 대해서 일차함수 -jx+B[j]를 생각하자. 일차함수들은 아래 그림처럼 convex hull trick의 형태로 관리할 수 있는데, [1, k]에 속하는 각각의 i에 대해 가장 큰 C_ij 값을 주는 j는 "해당 i에서 가장 위에 있는 직선"에 해당하는 j이다. 즉, 아래 그림과 같은 형태로 현재 convex hull에 있는 각각의 직선이 i의 특정 구간을 점유하는 형태이다.

직선 -jx+B[j]가 [s, e] 구간을 점유한다고 할 때, 여기서 얻을 수 있는 최댓값은 max(A[i] - ij) + B[j]의 꼴이니, convex hull 상의 모든 직선에 대해 저 최댓값을 multiset 등의 자료구조에 저장해 놓으면 multiset 원소의 최댓값이 지금 k에 대한 답이 된다.

이제 max(A[i] - ix) 꼴의 구간 쿼리를 효율적으로 처리할 수 있다고 가정하면 다음과 같은 형태의 풀이를 얻을 수 있다.

- k를 n부터 1까지 감소시키면서 -jx+B[j]들에 대한 CHT 자료구조를 관리한다.
- k를 하나 감소시킨 직후, -kx+B[k] 직선을 새롭게 자료구조에 추가한다. 추가하는 과정에서 빠지는 직선 (더 이상 점유하는 구간이 없는 직선)이 생길 텐데, multiset에서 해당 직선에 대한 최댓값을 빼 준다.
- -kx+B[k] 직선을 자료구조에 추가하면서 해당 직선이 점유하는 i의 구간 [s, e]를 구하고, 구간에서 max(A[i]-ik)+B[k]의 최댓값을 구한다. 해당 값을 multiset에 추가한다.
  (* convex hull에서 -kx+B[k] 바로 전에 있는 직선도 점유하는 구간이 바뀌기 때문에 역시 갱신을 해 주어야 함)
  (* B[k]가 너무 작아서 -kx+B[k] 직선이 자료구조에 아예 안 들어갈 수도 있으니 이 역시 고려)
- ans[k] = (지금 multiset 원소 중 가장 큰 것).

직선이 추가되고 삭제되는 횟수가 amortized O(n) 이기 때문에 시간복잡도가 보장이 된다는 사실을 우선 알 수 있다.

이제 방금 말한 구간 쿼리, 즉 [s, e]와 x가 주어졌을 때 max(A[i]-ix)의 최댓값을 구하는 것은 역시 CHT로 할 수 있다. 세그먼트 트리의 각 노드가 convex hull trick 자료구조를 담고 있으면 되는데, 초기에 각 i에 대해 i를 포함하는 노드에 대한 CHT 자료구조에 -ix+A[i] 직선을 업데이트 해주자. [s, e] 구간 쿼리가 들어오면 logn개의 노드에서 CHT query(x)를 호출하면 O(log^2n) 시간에 쿼리가 처리된다.

전체 시간 복잡도는 O(nlog^2n).