2023 IOI 멘토교육 1주차

BOI 2023을 돌았다.

Day 1

0:00 ~ 0:27

문제를 다 읽었다. 1번은 원 그려진거 보고 바로 넘겼고 2번은 인터렉티브라서 일단 넘겼다. 3번은 간단한 dp일 것 같다는 느낌을 받아서 3번부터 풀었다. 한 지점에서 p의 배수가 될 때까지 기다리거나 기다리지 않고 넘어가거나 둘 중 하나만 해도 되기 때문에 간단한 제곱 dp를 짤 수 있다. 이걸 짜면 27점을 받는다.

0:27 ~ 0:43

dp[i]  = min_{j<i} f(i, j) 꼴의 점화식이므로 i와 j에 대한 항으로 분리하면 최적화할 수 있다. a[i]%p와 a[j]%p의 대소관계에 따라 값이 약간씩 다르기 때문에 케이스를 나눠서 항 분리를 하면 된다. 나는 생각하기 귀찮아서 같은 경우, 작은 경우, 큰 경우 3가지로 나눠서 풀었다. 실수하면 시간을 많이 날릴 것 같아서 제곱으로 일단 짜서 검증했다.

0:43 ~ 0:52

아까 짰던걸 세그로 옮겼다. 100점을 받았다.

0:52 ~ 1:11

2번을 봤다. N<=50일 때 어떻게 풀지 먼저 생각해보았다. 1등과 2등이 싸울 때만 최댓값이 등장하기 때문에 이를 통해 1등 2등을 알아내고, 1등(또는 2등)과 i등을 비교하면 i등의 실력을 알 수 있다. 이후 100점 풀이를 고민했고, N=2인 상태부터 시작해서 N을 늘려가는 방식으로 푸는 접근을 시도했다. 1등과 2등에 대한 정보가 변할 경우, 쿼리를 두 번으로 이를 갱신할 수 있고, 그렇지 않으면 쿼리 한 번으로 갱신할 수 있다. 랜덤 데이터의 경우, 갱신되는 횟수는 로그번에 비례할 것이기 때문에 셔플하면 100점을 받는다.

 

"갱신되는 횟수는 로그번에 비례"에 대해 조금 더 생각해보자. 가장 간단하게 생각할 수 있는 추측은 1등과 2등이 실제로 $x$등과 $y$등일 때 앞으로 갱신될 횟수의 기댓값은 대략 $f(x, y) = \log _2(x) + \log _2(y)$라는 것이다. 갱신될 경우, 1등~(y-1)등 사이의 임의의 사람이 추가되어 갱신될 것이고, y/2등이 추가된다고 생각하면 $f(x, y) = f(x, y/2) + 1$이므로 잘 맞아떨어진다. 정확한 값을 구하려면 dp를 돌려서 $f(x, y)$를 $O(N^3)$에 계산해주면 된다. 추가로, 인자를 하나 더 추가해서 $t$번 갱신될 확률 $g(x, y, t)$를 계산하면 데이터 1개를 통과할 확률까지 계산할 수 있다. 문제 제한이 N+25이므로 갱신은 26번까지 허용되므로 $t = 26$까지 dp테이블을 채우면 된다.

 

N = 1500이고 초기 2명을 $\binom{N}{2}$가지 순서쌍 중 하나를 선택하는 방식으로 골랐다고 가정했을 때, 갱신되는 횟수의 기댓값은 약 12.782회이며, 데이터 1개를 통과할 확률은 99.986%이다.

 

1:11 ~ 1:57

1번을 고민해서 맞을 것 같은 세제곱로그 풀이를 얻었다. N<=700이라 안 돌 것 같았고 구현도 짜증나보여서 그냥 안 짜고 대회 창을 껐다.

 

Day 2

0:00 ~ 1:47

문제를 다 읽어봤지만 풀만해보이는게 없었다. 1번이나 2번이 쉬워보여서 고민해봤지만 1번은 이상하게 잘 풀리지 않았고, 2번은 46점 풀이에서 발전이 없었다. 1시간 30분시점까지 계속 고민하다가 일단 점수부터 긁기로 했다. 2번 46점 풀이를 짰고 운 좋게 디버깅 없이 바로 맞았다.

1:47 ~ 1:57

3번 비트dp를 짜고 11점을 받았다.

1:57 ~ 2:15

1번을 긁었다. 서브트리 크기를 기준으로 그리디하게 모든 루트에 대해 오일러 투어를 돌리면 해가 존재할 것이라는 추측을 코딩했고 실제로 점수가 긁혔다. 그러나 서브태스크 2의 점수만 긁히지 않았다.

2:15 ~ 2:32

밥먹으면서 틀린 이유를 생각해봤고 코드에서 몇 가지 오류를 발견했다. 서브태스크 2를 긁어서 78점을 받았다.

2:32 ~ 3:05

다른 문제는 이미 많이 고민했지만 답이 없는 것 같아서 1번을 조금 더 생각하기로 했다. 내가 점수를 처음 긁을 때 썼던 코드는 그리디하게 순회하지 않고 아무 순서로 순회한다는 사실을 발견했다. 이 사실을 이용하면 오일러 투어를 뽑고 시작점을 한칸씩 밀면서 O(N)에 값을 전부 구해줄 수 있다. 이를 코딩하고 100점을 받았다. 오일러 투어를 돌릴 때 서브트리 방문 순서가 상관 없다는 사실은 식 정리로 증명할 수 있고, 최적해가 오일러 투어라는 사실도 각 간선의 사용횟수가 3번이상이면 손해라는 것을 이용해서 증명할 수 있다.

3:05 ~ 4:11

2번은 계속 고민해봤지만 발전이 없었다. 3번은 뭔가 엄청난 dp를 세워야 100점을 받을 수 있을 것 같아서 고민해봤지만 잘 되지 않았다. w=1일 경우, 로컬에서 돌려서 전처리를 할 수 있기 때문에 길이 12이하인 모든 증가수열을 생성하는 방식으로 답을 구해봤다 (증가수열이어야 할 필요는 없지만 증가수열만 따져도 답이랑 일치했다). N=300일 경우 답이 바로 나왔고, 1400일 때는 3초정도 걸렸던 것 같다. 이를 이용하여 40점을 긁었다.

4:11 ~ 5:00

좀 고민하다가 걍 답이 없는 것 같아서 대회 창 끄고 꾸랑 놀았다.

 

참고로 Day 2 3번은 메모이제이션하면서 만드는 과정의 역순으로 백트래킹을 돌리면 시간내에 돈다고 한다.

총 점수는 0 + 100 + 100 + 100 + 46 + 40 = 386이다.