2022 ICPC Seoul Regional 인터넷 예선 후기

2등 했다.

2022 ICPC Seoul Regional 인터넷 예선에 HappyLastDance라는 팀으로 참여했다. 팀원은 UCPC 2021/2022 팀이랑 동일하게 군대 선임 두 분(stabilizer_h, harinboy)이다.

내년 봄학기에 졸업을 한다 치면 마지막 ICPC이기도 하고, 최근 여러 모로 실력이 예전같지 않음을 확인하면서 ICPC 준비를 열심히 해야겠다는 동기부여가 많이 되었다.

팀의 특성에 대해 잠시 살펴보자면, harinboy는 풀이 도출에 매우 강한 타입이고 stabilizer_h는 수학 문제 나오면 풀어달라고 영입한 (IMO 국대 출신) 조커픽(?)이기 때문에 거의 대부분의 코딩은 내가 하게 된다. 실제로 harinboy가 준 풀이를 내가 구현하는 것이 min(둘이 각각 혼자 푸는 시간)보다 적게 걸림을 실험적으로 확인하였다. 이런 팀 특성 때문에 생기는 취약점이 하나 있는데, 내가 망하면 팀이 그대로 망한다. 실제로 UCPC 본선 때 내가 웬 골드 그리디에 따운당해서 초~중반 페이스가 완전 말렸었다. 

아무튼 이런 경험들을 바탕으로 개인 연습을 많이 해야겠다고 생각했고, 혼자 codeforces gym에 있는 3~4시간 셋들을 몇 번 돌았다. 인터넷 예선은 시간이 짧은(3시간) 대신 쉬운 문제가 많이 나오고, 그것들을 실수 없이 빨리 풀어내야 어려운 문제를 풀 시간이 생기기 때문에 초반에 스코어보드를 따라가는 게 상당히 중요하다. 그래서 스코어보드를 보고 풀리는 문제를 빨리 따라서 푸는 연습을 위주로 했는데 대충 괜찮게 되어서 다행이었다.

대회 타임라인

인터넷 예선은 대대로 한글 번역이 있는 문제가 쉬운 문제들이었기 때문에, 일단 문제지를 받으면 한글로 된 것부터 내가 다 읽고 풀기로 했다.

대회가 시작하고, A가 한글 번역이 있길래 바로 읽었는데, 바로 짤 정도로 쉬운 문제였다. 뚝딱 짜서 냈더니 다행히 한 번에 맞았다(3min). 무려 퍼솔 ㄷㄷ

그 다음에 책상 위에 E(한글)가 올려져 있길래 읽고, 역시 바로 풀려서 짜서 냈다. 또 한 번에 맞았다(6min).

K도 한글이었는데 얘는 바로 생각은 안 나서 약간 고민을 하다가, 스코어보드를 봤더니 C가 풀리고 있길래 봤더니 얘도 한글이었다. C는 금방 풀려서 냈다. 한 번에 AC(13min)

G가 둘이서 게임 하는 DP 문제였는데, harinboy가 식을 빠르게 세워 주어서 그것을 코드로 옮겨서 냈더니 또 맞았다(19min). 얘도 퍼솔!

K를 다시 봤는데 이번에는 풀이가 생각이 났다. 그런데 짜서 냈더니 틀렸다. 그리고 나서 코드를 다시 보니 처음에 생각한 풀이는 같은 시간대의 간선을 여러 개 쓸 수 있을 때 맞는 거였다. 다익스트라 코드를 지우고 DP를 다시 짜서 내니까 맞았다(30min +1).

그리고 스코어보드를 봤는데 F가 풀리고 있어서 봤다. 처음에 조건을 하나 빼먹고 읽었던 걸 발견하고 나니 역시 별로 안 어려운 문제였고, cycle 처리할 때 방문 체크를 안 해서 TLE를 한 번 받고 맞았다 (39min +1).

여기까지 하고 나니 남은 문제들은 다들 아직 안 풀렸길래 다 한번씩 쓱 봤는데 다 어려웠다; 그나마 J가 좀 어디서 본 거 같이 생겨서 고민을 약간 했는데, 딱 봐도 루트 어쩌구 해서 푸는 문제였는데 trivial하진 않았다. 그렇게 약간 헤메다가 D를 읽었는데, 몇 달 전 코포에서 봤던 문제랑 똑같이 생겼다..? 잘 읽어 보니 진짜 똑같은 문제가 맞아서 일단 이걸 짜기로 했다. 그런데 그때 짰던 풀이가 완벽히 기억나지는 않아서 기억을 되살리는 과정에서 4번을 틀리고(...) 퍼솔을 할 수 있었다. (80min +4)

그리고 나서 다시 J를 보는데, 막혔던 부분 (루트보다 적게 들어있는 애들끼리 처리) 을 팀원한테 얘기하니 "이렇게 하면 되는 거 아님?" 하면서 문제를 바로 풀어주었다. 아 그렇네! 하고 짜서 냈더니 한 번에 맞았다. (93min)

이제 남은 게 B랑 H랑 I였는데, 셋 다 개노답인거 같아서 그냥 게임이나 켜고 싶어졌지만 참기로 했다. H를 "이렇게 하면 되지 않을까" 정도가 나와서 일단 내가 또 코딩을 하기로 했는데, 나중에 보니 그렇게 하면 안 되는 거였다. 이후 약간의 논의를 더 거친 후 "H는 못 푼다" 라는 결론을 내리고 그나마 누가 푼 B를 봤는데, 너무 풀기가 싫게 생긴 세팅이었다. 남은 시간동안 한숨 푹푹 내쉬면서 되도 않는 DP를 짜다가 대회가 끝났다.

후기

B는 침착하게 풀었으면 풀 수도 있었을 것 같은데, 대회 중에 그걸 하기에는 좀 어려운 듯 하다. D는 정말 코포 기출에서 1%만 바뀐 문제였고(풀이 완전 동일), H랑 I는 논문이랜다. 으휴!

초반 페이스가 말도 안 되게 빨랐어서 + 아는 문제가 나왔어서 결과가 좋게 나왔던 것 같다. 연습의 성과가 그래도 어느 정도 보여진 것 같아 다행이었다. 본선도 이렇게 잘 쳐지면 좋겠다. 그러려면 연습을 더 해야겠지?

문제별 풀이 (간단하게)

A

문제에 써 있는 대로 시뮬레이션을 하면 양쪽의 무게 차이가 얼마인지는 쉽게 알 수 있다.

가벼운 쪽에만 추를 올려서 무게를 맞춘다고 써 있으니 (참고로 영어 설명에는 안 써있다;;) 7종류의 무게추를 최소 개수로 조합하여 (양쪽 무게 차이)만큼의 무게를 만들면 된다. 무게 차이가 1000만 이하기 때문에 D[x] = (x를 만드는 최소 무게추 개수)로 정의하면 쉽게 구할 수 있다.

C

모든 i, j에 대해 |a[i]-a[j]| <= 1이 되도록 하려면 아래와 같이 배분하는 것이 유일한 경우의 수임을 알 수 있다.

- 모든 a[i]의 합을 S라고 할 때, (n-S%n)개는 [S/n], S%n개는 [S/n]+1

그렇게 되도록 최소한으로 옮기려면, a[i]를 크기 순으로 정렬한 다음 작은 것 (n-S%n)개가 [S/n], 나머지 S%n개가 [S/n]+1이 되도록 맞추어 주는 것이 최적이다. 목표 개수보다 많이 있는 더미에서 하나를 빼서 부족한 더미에 추가해주는 것을 반복하면 되므로 abs(a[i]-목표)의 합을 2로 나눈 것이 답이 됨을 알 수 있다.

D

https://codeforces.com/blog/entry/103493 여기서 1687D - Cute number 부분을 참고하면 된다.

농담이고, 일단 중요한 관찰은 "a[1]이 몇 번째 빨간색 구간에 갈지를 정하면 모든 깃발의 거취가 정해진다"라는 것이다. 좀 더 구체적으로 말하면, a[1]을 k번째 빨간색 구간으로 보내기로 정했다면 이 때 가능한 offset이 [st(k)-a[1], en(k)-a[1]]과 같이 구간으로 나타날 것이다. (st(k), en(k)는 각각 k번째 빨간색 구간의 시작점, 끝점) 이제 a[2]에 현재 가능한 offset의 구간을 적용해 보면 단 하나의 빨간색 구간하고만 겹친다는 것을 알 수 있다. (k번째 빨간색 구간 이후의 임의의 두 빨간색 구간은 적어도 k+1 이상 떨어져 있기 때문) 이를 바탕으로 offset 구간을 새로 설정하고 a[3]으로 넘어가고..를 반복하여 a[n]까지 왔는데 offset 구간이 살아있다면 그 때의 가능한 최소 offset이 답이 되는 것이다.

k를 1부터 증가시키면서 위 과정을 수행하면 우선 k가 a[n]보다 더 늘어나지는 않음을 알 수 있다. (a[n]번째 빨간색 구간의 길이가 a[n]이기 때문) 이제 k 하나당 위 시뮬레이션이 O(n)만큼 걸리는 것이 문제인데, a[i]와 a[i+1]이 다른 구간으로 가게 되는 i를 "Jump"라고 하면 Jump의 개수가 O(a[n]/k) 임을 알 수 있어서 같은 구간에 속하는 a[i]들을 잘 뛰어넘도록 구현을 해 주면 a[n] + a[n]/2 + a[n]/3 + ... a[n]/a[n] = O(a[n]log(a[n])) 라는 사실로 시간복잡도를 bound시킬 수 있다. 실제 구현 시에는 이분탐색 때문에 log가 하나 더 붙긴 하는데, 어떤 k가 답이 되지 않을 경우 보통 시뮬레이션이 훨씬 빨리 끝나기 때문에 수행 시간이 그렇게 오래 걸리지 않는다.

E

물건을 k개 산다고 하자. 할인을 어떻게 받는지는 나중에 생각하더라도 일단 가장 싼 k개를 사는 것이 제일 좋다.
이제 살 물건을 정했으니, 그 중에서는 가장 비싼 a개를 할인받는 것이 가장 좋다.
결국 우리가 시도해 볼 유의미한 조합은 다음의 n개밖에 없다.

- 1~max(0,k-a) 번째 물건을 정가로 산다. max(1,k-a+1)~k번째 물건을 반값으로 산다.

k를 하나 늘릴 때마다 새 물건 하나를 반값으로 사고, (k>a일 경우) 원래 반값으로 샀던 물건 하나를 정가로 사는 최대 2가지의 변경 사항이 있으니 이것을 갱신해주면서 예산이 b를 넘어가는 순간 멈추면 된다.

F

각 노드에서 나가는 간선이 최대 하나라는 매우 중요한 조건이 있다. 이 조건이 없다면 NP-Hard 문제가 된다... (Hamilton Path가 있는지 판별하는 문제보다 어려운 문제이다)

각 노드의 outdegree가 정확히 1인 그래프를 Functional graph라고 한다. Functional graph는 컴포넌트마다 사이클이 하나 있고 주변에 트리들이 달려 있는 형태로 생각할 수 있는데, 이 문제에서는 outdegree가 0일 수도 있으니 그냥 트리만 덩그러니 있는 컴포넌트도 존재할 수 있음에 유의하자.

아무튼 여기서 노드를 중복하여 방문하지 않는 최장경로는 반드시 (1) 트리에서 출발하여 루트에서 끝나거나 (2) 트리에서 출발하여 사이클에 도달한 후 한 바퀴 돌고 끝나는 두 가지 형태 중 하나이다.

따라서 각 트리마다 루트에서 가장 먼 노드까지의 거리를 구한 뒤 루트에서는 그 노드가 속한 사이클의 길이만큼을 더한 것이 (없다면 길이 1로 취급) 해당 노드를 지나는 경로 중 가장 긴 것이 된다. 이들을 모두 구해 최댓값을 출력하면 된다.

G

게임의 현재 상태는 (몇 번째 턴, 더미 1에 남은 돌의 수, 더미 2에 남은 돌의 수, 더미 3에 남은 돌의 수)의 4차원으로 표현된다. 각 상태마다 "그 상태에서 게임이 시작되었을 때 (선공 점수)-(후공 점수)"를 구하면 문제를 풀 수 있을 것이다. 각 더미의 돌 수는 100 이하이고 대충 넉넉잡아 50턴 안에는 게임이 무조건 끝나니 상태는 5000만개, 각 상태마다 가능한 전이가 최대 3개이니 4차원 DP로 문제가 풀린다.

J

점들을 x좌표별로 묶어서 보자. 적절한 상수 B를 정해서, B개보다 많이 들어있는 묶음 (Large) / 적게 들어있는 묶음 (Small)로 나누자.

Large - Large / Large - Small : 점이 각각 X개, Y개 들어있는 묶음 2개에 대해, 해당 묶음 쌍에서 생기는 직사각형의 개수를Z=min(X,Y)라고 할 때 O(ZlogZ) 시간에 셀 수 있다. 두 묶음에 공통으로 들어있는 y좌표의 개수를 k라고 할 때 k(k-1)/2개의 직사각형이 생기는데, k는 개수가 적은 묶음의 각 원소를 큰 묶음에서 이분탐색하는 방식으로 세면 된다.

Large 묶음은 많아야 N/B개 있으므로, 각 Large 묶음에 대해 "자신보다 크기가 작은 모든 묶음에 대해" 위 과정을 수행하면 총 시간복잡도가 O(N^2logN/B)이다.

Small - Small : 이 경우에는 묶음의 개수가 많아질 수 있으므로 다른 접근 방식을 취하자. 각 묶음마다 y좌표 2개의 순서쌍을 모두 구해서 늘어놓았다고 할 때 (예를 들어 y좌표가 각각 1, 5, 7이라면 (1,5), (5,7), (1,7)의 3개), 똑같은 쌍이 k개 있다면 답에 k(k-1)/2를 더하면 된다. 이 때 각 묶음에 점이 최대 B개 있기 때문에 쌍이 O(NB)개 생기고, 같은 쌍의 개수를 세는 것은 정렬 등의 방법으로 O(NBlog(NB))에 가능하다.

이제 B를 적절히 정해주어야 하는데, B=N^0.5로 설정하면 전체 시간복잡도가 O(N^1.5log(N))이 된다. N이 7만이라 어떻게든 제곱 아래로 떨구기만 하면 통과가 될 것이다.

K

d[i][j] = (시간 1~i에 해당하는 간선들을 사용하여 정점 j에 도달하는 최단 시간)으로 정의하자. 각 시간대마다 존재하는 간선 s-e (가중치 w)에 대해 d[i][s] + w가 d[i+1][e]에, d[i][e] + w가 d[i+1][s]에 각각 갱신된다. 또한 기본적으로 d[i][s]가 d[i+1][s]에 갱신된다. 이를 모든 시간대에 대해 해주면 O(t(n+m))에 문제가 풀린다.