Codeforces Round 806 (Div. 4)

Dashboard - Codeforces Round 806 (Div. 4) - Codeforces

 

F

ai < i 를 만족하는 원소에 대하여, i < j && i < aj 인 (i, j)의 개수를 세자.
배열의 원소를 왼쪽에서 차례로 볼 때, 현재 보고 있는 원소의 index를 j라고 하자.
수식 i < j && i < aj 의 의미를 다시 해석해보면 다음과 같다.
i := 이미 본 원소의 index
j := 현재 보고 있는 원소의 index
(i < aj 를 만족하는 i의 개수) := 지금까지 본 index 중 aj보다 작은 index

 

 

G

good key만을 사용하다가 bad key 만을 사용하는 것이 최적이다.

예를 들어 다음과 같이 key를 사용했다고 하자.

index	1	2	3	4
coin	a1	a2	a3	a4
key	g	g	b	g

case1) 위와 같은 상황에서 3, 4번 chests로부터 얻을 수 있는 코인은 다음과 같다.
a3//2 + (a4//4 - K)

case2) 한편 3번에 good key, 4번에 bad key를 사용했다면 얻을 수 있는 코인은 다음과 같다.
(a3 - K) + a4//2

따라서 good key를 bad key보다 먼저 쓰는 것이 최적이다.

한편, 3번째 이전 chests에서 어떤 키를 사용하였던 간에 위의 논리는 동일하게 적용된다.
(만약 앞서 bad key를 사용한 적이 있다면 case1, 2 논리에서 얻을 수 있는 코인의 양은 모두 1/2로 줄어들지만 대소관계예 영향을 미치지는 않는다). 따라서 수학적 귀납법에 의해 good key만을 사용하다가 bad key 만을 사용하는 것이 최적이다.

이제 최적의 방법으로 brute force를 시행한다. 이때 10^9//2^30 이므로 bad key 사용 이후 30번째 뒤 chests에서 얻을 수 있는 코인은 0이 된다. 이를 이용하여 brute force를 최적화하자.