2023 IOI 멘토교육 4주차

BOI 2022 Day 1을 돌았다.

0:00 ~ 0:17

1번 문제를 읽었다. 순열을 쿼리로 날리면 inversion 개수를 알 수 있을 때 N번 이하의 쿼리로 원래 순열을 복원해야한다. 순열을 N번 rotate하면서 넣으면 각 원소의 등수를 알 수 있기 때문에 쉽게 풀린다.

0:17 ~ 1:05

2번 문제를 읽었다. 섭태 풀이가 대부분 쉬웠고 100점 풀이도 쉬울 것 같아서 조금 고민해보기로 했다. 시작에서 끝으로 가는건 최적화하기 까다로워서 거꾸로 끝에서 시작으로 가는 방식을 생각해봤고 문제가 더 간단해졌다. 스파스테이블을 이용한 100점 풀이를 바로 짰고 AC를 받았다.

1:05 ~ 3:52

3번 문제를 읽었다. 가중치가 -M이상 M이하의 정수로 bound되어있을 때 M에 대한 다항시간으로 냅색을 해결해야한다. 1시간 넘게 고민해서 다항시간 풀이를 찾아냈다. 일단 x개를 뽑았을 때 최대와 최소 범위에 M가 속하는 최대 x를 이분탐색을 이용해서 찾을 수 있다. 이러한 x를 찾고 나면 좋은 성질이 성립하게 된다. 

일반성을 잃지 않고 x일 때 최소가 L과 M이하로 차이난다고 하자. (아닐 경우 최대가 그렇기 때문에 배열 뒤집고 L도 부호를 바꾸면 된다.) x일 때 최소를 선택한 상태에서 최적해로 바꾸는 시행을 생각해보면 어떤 원소를 추가하거나 제거하게 된다. 이러한 시행이 2M+2개 이상일 경우, 비둘기집의 원리에 의해 시행의 일부를 제거하는 것이 가능함을 보일 수 있다. 따라서, O(M)번의 시행으로 최적해로 만들 수 있다.

여기서 단순 냅색을 하게 되면 가중치 범위가 O(M^2), 시행 횟수가 O(M)이므로 dp table 크기가 O(M^3)이 되고, 각 원소별 최대 O(M)번 선택 가능하므로 O(M^2)번 전이를 하게 되어 O(M^5)에 문제를 해결할 수 있다.

비트셋을 이용하면 /64를 붙일 수 있고 M<=100까지 긁을 수 있다.

3:52 ~ 5:00

이후 100점 풀이를 찾으려고 M을 시간복잡도에서 떼려고 해봤지만 잘 되지 않았다. 결국 100+100+80=280점으로 끝났다.

 

3번 100점을 받기 위해서는 dp 정의를 약간 바꿔서 dp[S] = (현재 상태에서 가중치 변화량이 S이기 위한 최소 감소 개수)로 놓으면 상태가 O(M^2)가 되고 dp table 갱신도 O(M^2)만큼 걸리게 된다. 이를 아까처럼 O(M^2)번 하면 O(M^4)이고, 같은 가중치 원소를 덱dp를 이용해서 한번에 처리해주면 O(M^3)에 문제를 해결할 수 있다.