852 div2 virtual

Codeforces Round #852 (Div. 2)

Dashboard - Codeforces Round #852 (Div. 2) - Codeforces

A. 

어떤 빵집에서 첫째날에 구매하면 빵 하나에 a 금액, 둘째날에 구입하면 b 금액에 구매할 수 있다. 

빵 n개를 구매하는데 드는 최소 금액 

 

여기에 첫째날에 빵 구매하면 m개 구매할 때 1개를 보너스로 더 줌 

 

 

m+1개의 빵을 구매하는 금액인 a*m vs b*(m+1) 을 비교함 

 

왜냐 우선 a, b의 대소는 한눈에 알 수 있는데 m+1개의 빵을 구매할 때 첫째날이 더 합리적인지 

둘째날이 더 합리적인지 알고 싶어서 -> a,b의 대소 말고 변화를 주는 요인이 행사이기 때문에 자연스럽게 비교함

 

a*m < b*(m+1) 이라면 

n/(m+1) * (m+1) 개만큼 첫째날에 구매하고 나머지는 둘째날에 구매 

 

이런식으로 case work

 

B.

지역 최소들의 총 합, 지역 최대들의 총 합 이 주어졌을 때 만들 수 있는 원순열의 최소 길이와 원소들

(모든 인접한 원소들의 차이는 1, 지역 최소/최대 -> 어떤 원소가 양 옆의 원소보다 작을/클 경우)

 

관찰할 수 있는 부분 -> 예제 (Max-Min)*2 는 길이가 된다. 

 

이걸로 쉽게 접근하긴 했지만 

무조건 1씩 변화가 이루어지니 최대 -> 최소 -> 최대-1 

이런식으로 접근도 가능 

 

간단한 증명은 이제

 

지역 최대의 합 : a, 지역 최소의 합 : b (a 짝수)  

모든 경우에서 최대 -> 최소 -> 최대 -1 의 길이 a - b - a-1 

 

(a-b) + (a-1-b) + 1 = 2*(a-b)

 

어중이 -> 떠중이 -> 어중이 

 

이것보다 더 짧거나 같아야 한다는 것인데

 

최대가 아닌 최대의 절반인 절최로 해보자

 

절최 - 절최-1 - 절최 - b - 절최-1

이제 절최-1이 만든 변화를 지역 최소의 합 관점에서 관찰해보자.

 

b에서 b-(절최-1)이 되었다. 

 

a/2 - a/2-1 - a/2 - b-(a/2-1) - a/2-1

 

의 길이 

 

a/2-(a/2-1) + a/2-(a/2-1) + (a/2 - (b-(a/2-1)) + (a/2-1-(b-(a/2-1))) + a/2-(a/2-1)

 

= 2*(a-b)로 똑같이 된다. 

 

줄어든 만큼 늘어나는 것으로 보인다. 

그러므로 최대 - 최소 - 최대-1로 출력한다.

 

C.

 

[l, r]에서 처음과 마지막이 부분 수열의 최대 or 최소가 되면 안된다. 

 

관찰을 해보자. 

 

예제를 보다보면 무조건 안되는 경우가 있다. 

 

1 이나 n이  맨끝에 있는 경우이다. 

그렇게 1,n을 빼고나면 2, n-1이 안되는 경우이다. 

 

직관적으로는 와닿는데 설명을 엄밀하게 잘 못하겠다... 

 

위의 관찰을 통해서 [l, r]을 모든 범위로 잡고 투포인터 알고리즘을 이용해서 l을 늘려서 불가능한 경우를 없애고, r을 줄여서 불가능한 경우를 없앤다. 

 

정당한 방법인지에 대해서는 불가능한 방법만 없앴기 때문에 나온 결과는 정당하지 않을까 생각한다. 

 

D. 

 

 

MEX의 함수는 수열에 들어있지 않은 가장 작은 수이다. 

 

a,b 수열에 공통적으로 [l, r]의 부분 수열을 관찰할 때 MEX값이 같게 나오는 경우의 수 문제이다. 

 

MEX(l, r)의 결과값으로 1이 나오는 경우 2가 나오는 경우 차례로 생각을 해본다.

1이 나오는 경우는 1이 [l, r] 범위에 포함되지 않는 경우이다. 

2가 나오는 경우는 1이 [l, r] 범위에 포함되어 있으면서 2가 포함되어 있지 않은 경우이다. 

 

3은 1, 2가 [l, r] 범위에 포함되어 있으면서 3이 포함되어 있지 않은 경우이다. 

 

따라서 n을 조사하기 위해서 1, 2, 3, ... , n-1이 필요한 것을 알 수 있고 1부터 조사를 해나간다. 

l, r 범위를 점점 더 크게 만들어 나가며 경우의 수를 계산한다. 

 

1부터 조사한다는 생각을 하는 것이 이 문제의 키라고 생각하는데 자연스러운 과정이긴 하다. 

MEX의 함수 특징이 가장 작은 것을 확인하는 것이므로