1/27 - BOJ에 문제가 올라와서 올린다. 사실 글을 쓰는 지금 기준 safezone은 안올라왔는데 보니까 BIKO엔 있다.
글은 22일 쯤에 썼고 마지막만 약간 수정
기록용으로 좀 자세하게 서술한다.
내 점수는 12(grid) + 100(particles) + 45.4(roadwork) + 14(safezone) = 171.4로 11등이다.
이제 시간대별로 한 일을 서술하겠다. 정확하진 않아서 기억나는 대로 서술한다. 제출 시각은 선발고사 사이트에 적혀있는 대로 썼다.
0:00~0:30
문제를 쭉 읽었다. grid는 문제 이해만 10분 걸리는 더러워 보이는 문제였다. particles는 정확힌 모르겠지만 서브태스크를 봐서는 긁는 문제가 아닐까 하고 넘어갔다. roadwork는 일단 내가 싫어하는 경우의 수에다가 서브태스크는 11개로 겁나 촘촘해서 이것도 긁는 문제라고 생각했다. 마지막 safezone은 이해도 쉽고 웰노운처럼 보이길래 safezone부터 접근을 시작했다.
0:30~약 1:00 - safezone 고민
뭔가 유니온 파인드를 잘 관리하면 되지 않을까? 라는 생각이 들었다. 그리고 직사각형이니까 선 2개로 본 다음 스위핑하면서 집합을 어떻게 하면 될 것 같은데.. 아무리 생각해봐도 최악의 경우 O(N^2)인 풀이밖에 나오지 않았다. 서브태스크를 보니 N <= 100000 섭태가 있고 만점과 점수 차이가 큰 걸로 봐서는 "쉬운 문제가 아닐 수도 있겠다"라고 결론짓고, 그나마 쉬워 보였던 particles로 넘어갔다.
1:00 ~ 1:20 - particles 풀이 작성
생각보다 처음 볼 때 어려워 보였던 입자 충돌은 그냥 어떻게든 충돌만 시키는 거라서, 그냥 floor((개수)/2)라는 사실을 알 수 있었다. 그래서 결국 다음과 같은 짓을 할 수 있으면 된다는 걸 알았다.
1. 컴포넌트 중 1개에 +1
2. 어떤 정점을 기준으로 컴포넌트를 분할
할 때마다 각 컴포넌트당 floor((개수)/2)의 합 구하기
컴포넌트를 분할하는 횟수는 O(N)이니까 어떻게 되지 않을까? 라고 생각하다가 쿼리를 거꾸로 처리하면 편하다는 생각이 들었다. 하지만 그런 생각을 한 지 3초만에 함수 구현이라서 온라인 강제라는 걸 깨달았다. 그래서 결국에는 컴포넌트가 끊길 때 어떻게든 값들을 잘 관리해줘야 하는데..
어쨌든 분할은 naive하게 하면 될 것 같았다. 그럼 분할될 때마다 컴포넌트 당 입자 개수를 계산해줘야 하는데, 이걸 naive하게 하면 결국 O(N^2)이다. 그렇다면 제일 크기가 큰 컴포넌트만 빼고 다시 세주는 건 어떨까? 이건 small to large의 논리에 의해 O(NlogN)이 보장될 것으로 보였다. 풀이가 잡혔으니 디테일을 생각해봤다. 어떤 정점 v를 기준으로 분할될 때 v 자식들은 개수를 그대로 넘겨주면 되며, v 부모를 포함하는 컴포넌트의 경우 그 크기가 v의 서브트리 크기만큼 감소한다. 그리고 서브트리 크기를 관리하는 배열이 있다고 할 때, 이 컴포넌트 내부에서 v의 조상들이 v의 서브트리 크기만큼 감소해야 한다. 그렇다면 이 컴포넌트의 루트 -> v까지 경로에 -sz(v)를 해주면 될거고 이건 HLD..? 라는 결론이 나왔다. 어? HLD?
1:20 ~ 1:46 - particles 코드 작성
사실 선발고사 짜기 전에 알고리즘 몇개를 복습하고 들어갔다. 근데 HLD는 선발고사 들어가기 전에 한번 짜볼까 싶었는데 "설마 나오겠어" 라는 안일한 생각으로 안 짜고 들어갔다. (애초에 HLD 별로 안써봤다.) 그리고 이 순간이 정말 후회됐다. 하지만 어쨌든 HLD를 잘 관리하는 형태의 풀이가 나왔으니 HLD를 짜야만 했다. 그래서 몇개월 전에 짰던 HLD 코드의 기억과 HLD가 시간복잡도를 보장하는 원리.. 뭐 이런 것들을 토대로 어떻게든 HLD를 짜기 시작했다. 한 10분 정도 짜니까 그래도 얼추 맞는 것 같은 코드가 나왔다. 이제 이걸 토대로 복잡하게 그룹 분할, 가장 큰 컴포넌트 위치에 따른 케웍.. 뭐 이런 것들을 해주니까 어떻게든 코드가 완성되었다. 그리고 이제 예제 1을 돌리니까 RE가 떴다. 뭔가 그럴 것 같긴 했다. HLD에 약간 문제가 있다는 걸 알고 고쳤다. 그랬더니 답이 이상하게 나왔다. 또 열심히 고쳐줬다. 그렇게 최종적으로 코드를 완성했고, 제출 버튼을 눌렀다.
1:46 ~ 2:29 - 디버깅
0점이 나왔다. 와 진짜 멘탈이 터지지 않을 수 없다. 지금까지 짰던 풀이가 사실 다 틀렸던 거면 어떡하지? 라는 생각으로 결과를 눌러보니 RTE인데 섭태2만 WA였다. 엥? 하고 살펴보니 버그를 또 하나 찾았다. 고쳤더니 16점이 나왔다(섭태 2 점수). 근데 그래도 나머지 섭태는 다 RTE였다.
1:52 - 16점
2:04 - 16점
2:05 - 16점
2:08 - 0점
2:10 - 0점
2:14 - 16점
2:16 - 16점
2:18 - 16점
2:23 - 16점
이쯤 되면 사실 진짜로 풀이가 틀린게 아닐까? 싶었는데 드디어 치명적인 오류를 발견했다.
결론부터 말하면 HLD가 문제였다(...). 이래서 짜보고 들어가야 했는데
HLD 내부 세그는 오일러 투어로 정점을 인덱싱하도록 구현해놨는데 그게 아니고 정점 자체의 값으로 세그를 탐색하고 있었다! 그래서 트리가 일직선인 섭태2만 맞은 것이었다. 이걸 무려 40분만에 찾다니 나의 디버깅 실력을 다시 한번 의심했다. 그래서 냈더니 드디어 100점을 볼 수 있었다.
2:29 - particles 100점 (총 100점)
2:30 ~ 2:47 - 긁기 시작 (safezone)
100점을 그래도 하나 봤으니까 한결 마음이 편해졌다. 그렇게 쉬운 문제도 아니었던 것 같아서 이 때 마음속으로는 "이게 제일 쉬운 문제인가 아닌가"를 가지고 엄청난 갈등을 하고 있었다. 원래 전략이 가장 쉬운 문제를 풀고 나머지를 긁는 것이었기 때문이다. (통계적으로 보통 가장 쉬운 문제는 플~쉬운 다이아이다.)
그래도 일단 할건 해야하니까 긁기를 시작했다. 먼저 safezone. 거의 자명한 2번 섭태와 3번 섭태를 긁었다. 2번 섭태(7점)는 항상 음수 - 양수에 걸쳐있기 때문에 1차원에서 합치면 된다. 3번 섭태(7점)는 각 군부대 쌍마다 O(1)에 보면 된다.
2:47 - safezone 14점 (총 114점)
2:47 ~ 3:19 - 긁기 (roadwork)
이제 섭태가 무려 11개나 되는 roadwork로 갔다. 일단 문제 상태랑 입력을 문자열로 줘서 알아서 풀어야되는게 좀 귀찮았다. 그냥 이분매칭하면 10점 정도 줄 것 같았다. 그건 좀 비효율적인 것 같아서 다시 생각해보니 일단 최댓값을 O(N^2)에 찾는 LCS 비슷한 dp를 생각해냈다. 근데 이걸 생각하자마자 며칠 전에 풀었던 IOI'17 Wiring이 생각났다. 이것도 그룹을 하나로 보면 O(N)에 되나? 싶어서 Wiring과 비슷한 접근을 해봤는데 정확히 맞진 않았고, 대신 O(N)에 푸는 법을 찾는 데에는 도움을 주긴 했다. 간선을 기준으로 보게 되면, 이 간선의 포함 여부에 따라 점화식을 세울 수 있고 약간의 전처리만 하면 O(N)에 정말 쉽게 계산할 수 있는 식이 나온다. 이걸 구현해주면 최댓값만 구했을 때 얻는 점수인 40점을 얻는다.
3:19 - roadwork 40점 (총 154점)
3:19 ~ 3:40 - 방황
roadwork에서 경우의 수는 어떻게 세야 할까? 막 간선을 하나 제거하고 다른 간선을 붙이는 이상한 풀이만 생각났다. 빠르게 버리고 grid로 갔다. 근데 grid는 또 전혀 감이 잡히지 않았다. 섭태도 이상하고, 또 특정 형태 셀은 존재하지 않는다는데 어따 써먹는지도 모르겠다. 이걸 과연 긁을 수 있을까? 라는 생각에 다시 safezone으로 갔다. 섭태4는 x,y축에 평행한 선분끼리 잘 묶는 섭태였는데 이건 어떻게 할 수 있을까... 뭔가 비슷한 문제를 풀었던 기억이 있는데 디테일이 안잡혀서 버렸다.
3:40 ~ 4:19 - grid 긁기
그래도 grid가 0점이니까 섭태1은 긁어야 한다는 생각으로 긁기 시작했다. 좀 생각해보니까 섭태1은 어차피 형태가 정해져 있어서 X, Y만 찾으면 된다. 그리고 검은색이랑 흰색 경계에 쿼리를 잘 날려주면 그 값을 토대로 X, Y를 구할 수 있는 것 같았다. 그래서 열심히 구현하니까 12점이 나왔다.
4:19 - grid 12점 (총 166점)
4:19 ~ 4:31 - roadwork?
이제 할 수 있는 건 roadwork 아님 safezone이었다. safezone은 어려워 보였고 결국 roadwork로 왔다. 그냥 경우의 수를 naive하게 세는 것부터 긁자고 생각했고 브포를 짜서 5.4점을 긁었다.
4:31 - roadwork 45.4점 (총 171.4점)
4:31 ~ 5:00
roadwork 100점은 힘들어 보였고 safezone은 지금 시간 내에 풀이까지 짜서 구현해서 긁는 건 불가능했다. 그냥 멍때렸다.
후기
끝난 직후에는 그래도 다이아일 것 같은 particles를 풀었고, 긁을 만한 건 대부분 긁었고, 풀었어야 할 건 다 푼 것 같았다.
근데 스코어보드를 보니까 심상치 않았다.. roadwork 100점이 20명이 넘었다. 이때 딱 생각했다. "와 망했다"
난이도는 스코어보드 기준 roadwork << particles <<<< grid < safezone이었다.
아니 roadwork가 그렇게 쉽나? 난 모르겠던데.. 하고 있었는데 갑자기 max 구할 때랑 똑같은 dp로 풀릴 것 같다는 느낌이 왔다.
아
내 54.6점.............
아니 이럴거면 도대체 왜 섭태를 11개로 나눈거지? 제대로 낚였다. 그래도 나만 40점인 건 아니고 몇명 더 있으니까 그렇게 억울하진 않았다.... 라고 하고 싶은데 진짜 똑같은 dp로 풀리니까 아직도 어이가 없다. 이번엔 진짜 할거 다 했다고 생각했는데.. 그게 아니었다. 멍때릴 시간에 생각이나 좀 더하지
그리고 생각해보니까 이거 어디서 본 상황이다. 1년 동안 발전이 없네 ㅋㅋ
