APIO 2019 후기

작년 KOI에서 은상을 타서 올해는 APIO를 나갈 수 있었다.

대회 일주일 정도 전부터 예전 APIO 문제들을 좀 보긴 했는데... 진짜 풀기는 커녕 부분점수도 못 받을 것 같은 문제들이 많았다.
어떤 해는 세 문제 중에 하나도 엄두가 안 나고, 어떤 해는 그래도 한 문제 정도는 풀만하기도 한걸 보면 난이도가 좀 오락가락 하나보다.

그리고 대회 때 비주얼스튜디오를 써야한다고 했는데 나는 비주얼스튜디오밖에 쓸 줄 몰라서 오히려 좋았다.

1. 이상한 기계

처음엔 보자마자 대체 뭔 소리인지 이해가 안 돼서 일단 다른 문제들부터 다 읽었다. 근데 다른 문제들이 더 멀어보여서 다시 이 문제로 돌아왔다.
일단, 주어진 구간들이 겹칠 수 있다. 그러므로 라인 스위핑을 써서 합쳐야되긴 할 것 같다. 그런데 그건 부가적인 문제고, 문제의 핵심은 서로 다른 순서쌍을 어떻게 셀 것인지에 대한 것이다.
바로는 생각이 안 나서 그냥 쌩 구현으로 긁어놓을까 생각해보다가 어차피 시간이 5시간이나 있으니 좀 더 고민해보기로 했다.

처음 생각난 것은, \(10^{18}\)크기의 구간을 다 도는 것은 불가능한데 그러면 이 문제는 사이클을 찾으라는 것 아닐까? 라는 생각이었다.
사이클을 찾아야겠다고 생각해보니 두 가지를 해결해야 했다.
1. 사이클의 길이는 어떻게 구할까? \(10^{18}\times 10^{18}\) 길이의 사이클도 있을 수 있다.
2. 사이클의 길이를 구했다고 쳐도, 그러면 사이클 안에서도 같은 순서쌍이 있을 수 있지 않을까? 그건 어떻게 구별할까?
의외로 1번을 고민하다보니 2번이 먼저 해결됐다.일단 \(t=0\)일 때는 \((0,0)\)이니까, 사이클을 찾을 때는 다음에 나오는 \((0,0)\)을 찾으면 된다. (무조건 돌아오기는 한다.)
그런데 2번 고민처럼 \((0,0)\)이더라도 \(t \bmod B\)가 다르다면 \(\lfloor \frac{t}{B}\rfloor\)가 다른 시점에 바뀌어서 사이클이 아니지 않나? 라는 생각을 잠깐 했다.
근데 순서쌍의 두번째 성분이 의미하는 바가 \(t \bmod B\)이니, 당연히 두 순서쌍이 같으면 사이클이 된거고 그렇다면 둘 사이에는 같은 순서쌍이 있을 수 없다.

이 생각까지하고나니 이제 문제를 해석했다는 느낌이 들었다. 이제 이 문제는 "\(t=0\) 이후로 가장 처음나오는 \((0,0)\)은 몇 번째인가?" 를 묻는 문제가 됐다.

\(((t+\lfloor \frac{t}{B}\rfloor)\bmod A, t\bmod B)\)가 언제 \((0,0)\)이 될까?
두번째 성분이 훨씬 간단한 식이니 두번째부터 \(0\)으로 만들자는 생각을 했다.

순서쌍을 \((0,0)\)으로 만드는 \(t\)를 \(T\)라고 해보자. 그러면 \(T\bmod B=0\)이므로 \(T=Bx\)라고 둘 수 있다. 물론 \(x\)는 음이 아닌 정수다.
그러면 \((T+\lfloor \frac{T}{B}\rfloor)\bmod A=0\)에서 \(T\)를 바꿔주면
\((Bx+\lfloor \frac{Bx}{B}\rfloor)\bmod A=(Bx+x)\bmod A=(B+1)x\bmod A=0\)이다.
그러면 이제 \((B+1)x=Ay\)라고 두면, 가장 작은 양의 정수쌍 \((x,y)\)만 찾으면 사이클의 길이를 구할 수 있다. 그리고 이 이 정수쌍은  \((B+1)\)과 \(A\)의 최소공배수에서 각각 \((B+1)\)과 \(A\)를 나눈 것이다.

\(G=\gcd(B+1,A)\)라고 하면 최소공배수 \(L=\frac{(B+1)A}{G}\)이고 \(x=\frac{L}{(B+1)}\)인데, 구하고자 하는 사이클의 길이는 \(Bx\)이므로 결국엔 \(\frac{(B+1)AB}{G(B+1)}\)이고 약분해주면 \(\frac{AB}{G}\)가 사이클의 길이다.

근데 \(A\)와 \(B+1\)이 서로소라면 \(\frac{AB}{G}=AB\)라서 오버플로우가 나는데 왜 맞는지 모르겠다.
우연히 잘 처리가 돼서 맞았을 수도 있겠지만 분명히 그런 경우에 답이 음수가 나오는 걸 봤는데... 제출했더니 맞아서 그냥 넘어갔다.
끝나고 \(AB\le 10^{18}\)였는데 잘못봤겠지 하고 넘어갔는데, 공개된 문제를 보니 \(A,B \le 10^{18}\)가 맞다...
사이클 길이가 \(10^{18}\)을 넘는지만 판별하면 똑같은 풀이를 적용할 수 있긴 하지만 왜 그걸 처리 안 해도 맞았는지 모르겠다.

2. 다리

서브태스크는 아마도
1. 제한 작음
2. 주어지는 그래프가 체인(선형)임
3. 주어지는 그래프가 완전 이진트리임
4. 2번 쿼리만 주어짐
5. 주어지는 그래프가 트리임
이었고, 나는 1, 2, 4번을 긁었다.

1번은 그냥 모두 탐색하는 것으로 구현하면 된다.
2번은 더 간단하게 푸는 방법이 물론 있겠지만 나는 진짜 어거지로 풀었다.
일단 선형이니 세그먼트 트리로 연속된 간선들의 최솟값을 구할 수 있다.
그러면 1번 쿼리는 트리를 업데이트하면 간단히 된다.

2번 쿼리는 이분탐색을 썼다.
\(s_j\)번 정점에서 출발해서 왼쪽, 오른쪽으로 몇 개의 정점까지 갈 수 있는가? 로 생각해서,
\(m\)개의 정점까지 갔을 때 최솟값을 세그먼트 트리로 구해서 무게제한보다 큰지 확인하면서 \(m\)의 최댓값을 구해주면 된다.
머리속으로는 되겠는데... 구현을 해보려니 세는건 \(n\)개의 정점이고 최솟값은 \(n-1\)개의 간선에서 찾는거다보니까 뭔가 머리가 꼬여서 짜는게 너무 힘들었다.
근데 체인에서 되면 트리를 HLD로 나눈다음에 잘 하면 되지 않을까? 또 트리에서 되면 그래프에서 MST만 뽑아내서 어찌저찌 할 수 있는거 아닐까? 라는 생각에 고민해보다가 체인으로 나눈다고 더 나아지는 점이 전혀 안 보여서 포기했다.
4번은 쿼리를 오프라인으로 처리해봤다.
2번 쿼리만 있으니 무게제한 순으로 쿼리를 정렬한 뒤에, 그래프에 지나갈 수 있는 간선을 추가해가는 방식으로 하면 된다.
그러면 유니온파인드로 그룹을 합친다고 생각해서, 현재 정점이 속한 그룹의 크기만큼이 방문할 수 있는 정점이다.
이게 2번보다 훨씬 간단했다.

이렇게 긁으니 43점을 받았다.

3. 가로등

서브태스크는 아마도
1. 제한 작음
2. 2번 쿼리의 \(b=a+1\)임. 즉 인접한 두 지역에 대해서만 주어짐.
3. 1번 쿼리의 결과로 가로등이 켜지기만 함
4. 1번 쿼리부터 다 하고 2번 쿼리가 주어짐
이 중에서 1, 2, 3번을 긁었다.

일단 마찬가지로 1번은 그냥 구현하면 된다. 모든 순서쌍을 매 초마다 다 세줬다. 
2번은 이제 어떤 가로등이 얼마나 오래 켜져있었는가를 묻는 문제가 된다. 이 것도 매 초마다 세주면 당연히 시간초과다.
그래서 매 초 세지 말고 쿼리가 들어올때만 이 가로등이 언제부터 지금까지 켜져있었는지(꺼져있었는지)를 업데이트해주면 된다.
그리고 업데이트한 시점을 저장해두면 다음에 쿼리가 들어왔을 때 다시 계산할 수 있다.

3번은 좀 고민을 해봤는데, 이 것도 세그먼트 트리를 쓰면 구할 수 있다.
\(a\)부터 \(b\)까지 간선이 다 켜져있어야 운행할 수 있는데, 다 켜져있는지는 둘 사이에 켜져있는 가로등의 개수를 세그먼트 트리로 저장해두면 된다.
그러면 언제부터 다 켜져있었는지는 같은 방법으로 둘 사이에 있는 가로등 중 가장 늦게 켜진 가로등을 세그먼트 트리로 구하면 된다.
대회 남는 시간은 계속 이 문제만 고민했던 것 같은데 아직도 모르겠다.
요즘엔 쿼리문제가 어려워보이면 쿼리를 정렬하고 오프라인으로 될까를 생각하고 있는데 이 문제는 순서가 중요하니 정렬해버리면 꼬여버릴 것 같고...

그래서 총합 203점을 받았다.
처음엔 별 생각 없었는데, 집에 가서 작년 결과들을 찾아보다보니 203점이면 가능성있지 않나? 라는 생각이 자꾸 들었다. 그런데 아는 사람이 없으니 점수비교를 해볼수도 없고...
그냥 기대만 하다가 슬랙에서 다른 분한테 여쭤보니 203점이 엄청 많다는 이야기를 들었다. 그래서 조금 마음이 놓였다.

그러다 25일에 점수가 나왔는데,

진짜 동점자가 엄청나게 많아서 등수가 높게 나왔다.
KOI에서도 동점자를 다 올려줘서 은상을 받았는데, 여기서도 동점자를 다 올려준 덕분에 덩달아 올라갔다.
아무튼 나로선 매우매우 좋은 결과라서 기쁘다.

결국 은상을 탔다!