CEOI 2019 Day 1

최종 스코어보드 (내 이름 가림)

어제 저녁 7시부터 12시까지 지인들이랑 CEOI 2019 Day 1 셋 버춸을 돌았다. 버춸 돌기 전에 내가 너무 못할까봐 걱정이 많이 됐는데 생각보다 점수가 엄청 잘 나와서 기분이 좋다. 특히 3번문제는 백준에서 다1문제인데(Dynamic Diameter) 운이 좋아서 풀이를 빨리 찾을 수 있었다.

참고로 플랫님은 3번 73점까지 풀이를 아는데 구현을 안 했다고 하고, 이환님도 73점 아는데 귀찮아서 안 했다고 한다 ㅋㅋ;

 

0:00 ~ 0:13

난이도 순서를 모르기 때문에 문제를 차례대로 읽으면서 나이브 + 인간섭태를 차례로 긁고, 그나마 쉬워보이는 문제에서 더 점수를 긁는 방식으로 전략을 세웠다. oj.uz에도 한국어 지문이 없어서 영어 지문을 읽어야 했지만 문제 내용이 간단해 빠르게 읽을 수 있었다. 일단 A를 읽은 후, t = 1일때만 긁는 것이 낫겠다고 판단을 했고, 제곱 or 제곱로그 섭태까지만 긁고 다음문제를 읽어보기로 결정했다.

t = 1인 경우, 가능한 건설 순서를 아무거나 찾기만 하면 되고, 건물들로 둘러싸이면 안 된다는 조건 때문에 연결성분의 개수를 1개로 유지하면서 가장 왼쪽 아래 점을 고르는 그리디를 생각했다. 간단하게 증명을 해보려고 했지만 증명이 잘 안 되었고, 직관적으로는 성립하는 것 같아 믿음을 가지고 짜서 제출을 해봤다. (이때까지만 해도 내 풀이가 제곱로그인줄 알았다.)

제출을 하고 나니 54점이 긁어졌고, 코드를 다시 보니 내 풀이가 O(NlogN)이여서 54점을 날먹하고 다음 문제로 넘어갔다.

0:13 ~ 0:25

B의 서브태스크를 보니 N은 의미가 없고, 문자열에 나타날 수 있는 문자의 가짓수 K가 중요하다는 것을 알 수 있었다. 자명한 O(K^8) 풀이를 짜면 21점이 긁어진다는 것을 쉽게 알 수 있었고, 그 다음 섭태들의 풀이를 생각해봤지만 잘 떠오르지 않아 일단 C로 넘어갔다.

0:25 ~ 0:59

C의 문제 내용은 매우 간단했다. 트리가 주어지고, 간선의 가중치 업뎃 쿼리가 주어질 때, 트리의 지름을 온라인으로 계산하는 문제다. O(QN) 나이브를 짜면 24점을 긁을 수 있고, 섭태 3, 4, 5의 풀이도 되게 쉬운 편이였다.

섭태 3은 트리가 스타 그래프 형태인 섭태였고, 이는 단순 max 세그를 이용하면 쉽게 풀 수 있다.

섭태 5는 점 1을 지나는 지름이 항상 존재하는 섭태였고, 이 섭태는 오일러 투어 트릭+1까지의 거리를 담은 max 세그를 이용하면 풀 수 있다.

섭태 4는 주어지는 트리가 균형 이진 트리인 섭태였는데 이 섭태가 개인적으로 제일 까다로웠다. 처음에 생각했던 방법은 각 서브트리별로 세그를 만들어서 관리하는 방법이였고, 이렇게 하면 아마도 쿼리당 로그제곱에 풀 수 있을 것이다. (이환님은 이 섭태를 안 긁어서 49점이였다.)

 

여기까지 생각했을 때 대략 35분 경과했을 때였고, 풀태를 제외한 섭태가 남아있지 않아서 45분까지 풀태를 좀 생각해보기로 했다. 45분까지 풀태를 계속 생각하다보니 섭태 4에서만 시복이 보장되는 사풀들이 좀 나왔고, 풀태 각이 보일 것 같아서 조금 더 잡아보기로 했다.

한 50분쯤 경과했을 때 그냥 섭태를 일단 긁어놓고 풀태를 생각하기로 결심했고, 빠르게 코딩을 해서 59분에 24점을 긁었다.

 

0:59 ~ 3:06

24점을 긁은 다음, 더 긁기가 귀찮아서 풀태를 다시 생각해봤다. 섭태 4에서만 성립하는 사풀들을 잘 생각해보니 이를 약간 변형하면 될 것 같다는 생각이 들었고, 센트로이드 분할을 박았더니 문제의 풀이를 찾은 것 같았다.

 

내가 찾은 풀이는 다음과 같다.

일단, 센트로이드 분할을 박아놓고, 현재 센트로이드 cent에 있을 때, cent에서 제일 멀리 있는 점 v를 세그를 통해 찾는다. 그다음 v-u 경로 상에 cent가 있으면서 cent로부터 제일 멀리 있는 점 u를 찾고 ans에 v-u 거리를 갱신해준다. (이러한 u가 없으면 v-cent 거리를 갱신해준다.) 그다음, v가 있는 서브트리의 센트로이드로 이동해서 반복한다.

 

이 풀이를 잘 생각해보면 널리 알려진 트리의 지름 구하는 알고리즘이랑 동일하게 작동하는 것을 알 수 있다.

처음에 임의의 점 x (이 풀이에선 초기 센트로이드)를 잡은 후, x로부터 가장 먼 점 y를 잡고, y에서 가장 먼 점까지의 거리를 센트로이드별로 분할해서 logN번의 쿼리로 찾는다는 것을 확인할 수 있다.

 

업데이트는 센트로이드마다 세그의 특정 구간을 갱신해주면 되고(오일러 투어 테크닉으로 세그를 펼쳐놓으면 구간 업뎃으로 변한다), 갱신해야 하는 센트는 O(logN)개이므로 총 시간복잡도 O(NlogN+Qlog^2N)에 문제를 해결할 수 있다.

 

이 풀이를 찾았을 때는 대략 1:20쯤 경과했을 때였던 것 같고, 대략 2:00쯤까지 구현을 했다. (센트로이드의 구현이 기억나지 않아 뇌절을 좀 했다.) 그 다음 예제로 디버깅을 하는데 예제 2의 마지막 쿼리만 자꾸 이상한 큰 값이 나왔고, 한참동안 그 원인을 찾지 못하고 있었다. 풀이에서 지름의 끝점을 고정시키고 센트분할을 돌려야 하는데 고정을 안 시켜서 답이 틀린줄 알고 지름의 끝점을 고정시켜봤지만 여전히 동일한 값이 나와서 멘탈이 좀 흔들렸다.

 

좀 생각을 해보니 지름의 끝점을 고정시키지 않아서 문제가 생긴거라면 더 작은 값이 나와야 정상인데 그렇지 않았고, 지름의 끝점을 고정시키지 않아도 반드시 지름의 끝점이 선택된다는 것을 알 수 있었다. 그렇게 맞왜틀을 계속 하다가 나이브 코드와 비교해보니 간선 업데이트가 이상하게 된다는 것을 확인했고, 알고보니 세그에서 propagate 과정 도중 lazy를 자식들에게 더해줘야 하는데 그냥 값을 바꿔버려서 틀렸다는 것을 알게 되었다... (이때 이걸 발견하고 욕을 엄청 한 것 같다 ㅠㅠ)

 

+ 기호를 추가했더니 예제가 잘 나왔고, 제출을 해봤지만 TLE를 당했다. 지름의 끝점을 고정시키지 않은 기존 풀이로 재제출하니 더 빨리 돌았지만 여전히 TLE가 났고, map을 unordered_map으로 바꿔주니 AC를 받을 수 있었다.

 

3:06 ~ 3:24

다시 2번으로 돌아와서 빠르게 나이브 코드를 짜고, 21점을 긁었다. (oj.uz 푼 사람 수로 스포를 당했지만) 1번 문제는 어려운 것 같아서 남은 시간을 2번에 올인하기로 했다. 이때 스코어보드를 보니 이환님은 이미 B 100점을 받은 상태였다.

 

어느 정도 점수가 안정권에 진입한 것 같아서 디스코드를 잠깐 열어봤는데, 친목 서버에서 내가 C 100을 받았다는 것에 대해 엄청 놀라워하고 있길래 처음에 좀 의아했다. 알고보니 C번이 백준 티어로 D1이였던 매우 고난도 문제였고, oj.uz 솔브수가 많았던건 그냥 유명한 문제라서 그랬던 것이였다 ㅋㅋㅋㅋ

 

3:24 ~ 3:52

다이아 1을 풀어서 기분이 좋은 상태로 2번을 고민해봤고, 섭태 2나 3은 뭔가 추한 풀이 밖에 안 떠오르는 것 같아서 풀태를 고민해봤다. 풀태는 K=62라 상수 작은 네제곱을 짜면 돌 것 같았고, 시복을 고정해놓고 생각하니 풀이가 떠올랐다.

정육면체의 꼭짓점을 체스판 컬러링 하고 같은 색의 점들의 알파벳을 고정해놓으면, 전처리를 통해 O(K^4)에 답을 구할 수 있다는 것을 알아냈다.

그래서 코드를 빠르게 짜고 제출을 해봤지만 1번 데이터에서 TLE가 났고, K의 값을 62에서 52로 줄이니 84점이 긁혔다.

 

3:52 ~ 4:26

30분간 열심히 상수커팅을 했다. 프라그마, register int, 조건문을 넣어서 최대한 MOD연산 줄이기 등 할 수 있는 최적화는 다 박았고, 운 좋게 1097ms로 100점을 받을 수 있었다. (이 문제는 TL이 1100ms였다.)

 

이환님께 들은 풀이는 for문을 돌때 i, j, k, l이 단조증가하도록 4중 for문을 도는 풀이였고, 이 풀이로 제출하면 매우 넉넉하게 통과가 된다. (약 200ms 정도)

 

여담으로 oj.uz 서버가 느린건지 백준 서버가 빠른건지 잘 모르겠지만 register int와 pragma를 안 박고 조건문으로 MOD연산 줄이기만 한 코드를 백준에 제출하니 844ms에 도는 것을 확인할 수 있었다... (pragma 박으면 792ms)

 

4:26 ~ 5:00

1번을 풀까 생각했지만 귀찮아서 그냥 안 풀기로 하고 걍 디코하면서 놀았다. ㅎㅎ

 

느낀 점

내 원래 실력보다 훨씬 잘 봐서 기분이 엄청 좋다 ㅋㅋ 센트로이드 분할과 같은 어려운 알고리즘을 이용해 문제를 풀어서 재밌었고, 극한의 최적화를 통해 아슬아슬하게 100점을 받는 것도 되게 재밌었다. (추하다고 느낄 수 있는데 정풀이랑 시복 같잖아요 ㅡㅡ)

문제 퀄도 나쁘지 않았고 풀이는 쉬운데 구현은 더러운 문제도 없어서 전체적으로 좋은 셋이라고 생각한다. (사실 3번 구현이 약간 복잡하긴 한데 구현 때문에 빡치는 문제는 아니였다.)