Baltic Olympiad in Informatics 2022 Day 1 연습

1월 22일 오전 4시부터 9시까지 BOI 2022 Day 1을 돌았다.

 

42 / --

A를 빠르게 밀고, B를 뻘짓처음으로 template를 써서 구현하다가 30분 동안 컴파일 에러를 고치고, C의 풀이를 한시간 반만에 내고 4시간만에 올솔...... 하는 줄 알았으나, 관찰 하나를 잘못해서 결국 셋이 끝난 9시 53분경에 AC를 받았다.(5시간 53분)

 

OI 셋을 오랜만에 돌았지만, 역시 OI 문제들이 제일 영양가 있다. 사고를 깊게 해야하고, 서브태스크를 통해 단계적인 관찰을 할 수 있다.

 

 

 

A - Art Collections

 

인터렉티브 문제이다.

1부터 N까지의 순열을 publish 함수에 넣으면 inversion의 개수를 리턴할 때, 실제 순열을 구하라는 문제이다. publish 함수는 최대 N회까지 호출할 수 있다.

 

 

Solution

 

순열의 첫 번째 원소만 맨 마지막으로 옮기면 해당 원소의 순서를 알 수 있다. 실제 순열에서 i번째 원소였다면, 해당 원소에 대한 inversion의 개수는 $i-1$개에서 $N-i$개로 변하기 때문에, 두 순열의 리턴값을 통하여 i를 구할 수 있다.

{1, 2, ..., N}을 계속 rotate하면서 publish함수에 넣어주면 정확히 N회의 호출을 통해 AC를 받을 수 있다.

 

 

 

B - Event Hopping

 

$i$번 행사는 $[S_i, E_i]$ 시간에 진행되며, $i$번 행사에서 $j$번 행사로 넘어가기 위해서는 $i$번 행사가 끝나고 나서 넘어갈 수 있다. 즉, $S_j \leq E_i \leq E_j$를 만족하는 경우에 넘어갈 수 있다.

"$s$번 행사에서 $e$번 행사로 넘어가기 위해서 거치는 행사의 개수의 최솟값을 구하여라"라는 쿼리를 Q개 처리해야 한다.

 

 

Solution

 

$s$번에서 $e$번으로 내려가는건 조건이 너무 빡빡하니깐, $e$번 행사에서 $s$번 행사로 역으로 거슬러 올라오는 것을 생각해보자.

 

세그트리를 통해 어떤 구간에서 한 번 올라갔을 때 도달할 수 있는 '최소의 왼쪽 끝점을 가진 행사'를 계산할 수 있다.

그렇다면 이를 스파스 테이블로 저장하여 각 구간에서 $k$번 올라갔을 때의 행사 또한 $O(logN)$에 구할 수 있다.

그렇다면 이를 (LCA를 구하듯이) 이분탐색하여 각 쿼리를 $O(logN)$에 처리할 수 있다.

 

-1 처리와 0 처리에 유의하자. ($s = e$인 쿼리가 실제로 예제에도 주어진다.)

 

 

 

C - Uplifting Excursion

 

배낭채우기를 한다. 그냥 하면 재미없으니, 각 물건의 무게는 $[-M, M]$($-300 \leq M \leq 300$) 범위이며, 정확히 $L$($-10^{18} \leq L \leq 10^{18}$)의 무게를 맞춰야 하고, 각 물건의 개수도 굉장히 많다(무게 $l$인 물건에 대하여 개수를 $A_l$이라 하였을 때, $0 \leq A_l \leq 10^{12}$). 이 때 챙길 수 있는 물건의 최대 개수를 구하여라.

 

 

Solution

 

일반성을 잃지 않고, 물건들의 무게의 총합이 $L$ 이상이라고 가정할 수 있다. 아닐 경우, 물건들의 무게와 $L$ 각각에 -1을 곱해주면 된다.

 

무게가 작은 물건부터 보면서, 무게가 $L$을 넘지 않으며 채울 수 있는 최대한으로 물건을 채운다.

 

이제부터 중요한 부분인데, 남아있는 물건들을 이용해서 무게 $[-M^2, M^2]$ 구간에서의 배낭채우기를 수행한다. 또한, 이미 사용한 물건들을 '개수가 -1이고 무게가 -(원래 무게)'인 물건으로 정의하여 배낭채우기에 추가한다. 최종적으로, 남아있는 배낭의 capacity를 $[-M^2, M^2]$ 구간에서의 배낭채우기를 통해 채워준다.

 

위의 알고리즘으로 정확한 답을 구할 수 있는 이유는, 물건의 개수가 무한대일 경우 $M^2$ 이상이며 (모든 물건의 무게의 최대공약수)의 배수인 무게는 항상 채울 수 있기 때문이다. 이를 통해, 물건의 개수가 $M^2$ 초과로 많더라도 무게가 $M^2$인 지점까지만 확인해주면 된다는 것을 알 수 있다.

 

마지막으로, 그냥 배낭채우기를 하면 $O(M^4)$지만(Subtask 5), 무게가 $w$인 물건을 여러 개 추가할 때 $mod w$로 동일한 무게의 칸끼리만 영향을 준다는 것을 생각해 보면, deque을 통하여 $O(M^3)$으로 최적화 할 수 있다.