Codeforces Round 702 (Div. 3)

Dashboard - Codeforces Round 702 (Div. 3) - Codeforces

 

 

E

방법 1 -  greedy

두 사람에 대해 [token이 많은 경우를 강하다, 적은 경우를 약하다]라고 표현하도록 하자.

어떤 사람 a가 우승하는 경우를 생각해보자. a가 참가하지 않은 경기가 일어나는 것은 a에게 불리하다. 왜냐하면 결국에 만나야하는 상대의 능력치가 증가하기 때문이다. 

따라서 어떤 사람 a가 우승할 수 있는지는 다음과 같은 greedy 방식으로 확인이 가능하다.
a가 능력치가 낮은 순으로 모든 상대와 대결했을 때 우승할 수 있으면 우승 가능하고 그렇지 않으면 우승 가능하지 않다.

index	1	2	3	4	5
a[i](token value)	2	3	5	9	20
req	max(2, 1)	max(3, 3)	max(5, 6)	max(9, 11)	20

한편, 위와 같은 예시에서 token값이 높은 것부터 낮은 순으로 (i와 대결했을 때 우승하기 위한 최소 요구 능력치)인 req[i] 값을 구해보자.
req[i] :=  (i와 대결했을 때 우승하기 위한 최소 요구 능력치)

먼저 가장 강한 상대와 붙어서 우승하기 위해서는 그보다 강하거나 동등하면 된다.
req[5] = 20

두 번째로 강한 상대와 붙어서 우승하기 위해서는 일단 적어도 두 번째 상대보다 강하거나 동등해야 한다. (req[4] >= 9) 
우리는 위에서 설명한  greedy 방식으로 대결 할 것이고, 두 번째로 강한 상대를 이기면 가장 강한 상대와 붙게 된다.
이때 두 번째 상대의 능력치를 흡수하고 대결하게 되므로 req[5]-9(두 번째 상대의 능력치)보다 강하거나 동등하면 우승 가능하다.
req[4] = max(9, req[5]-9) = max(9, 11) = 11

이제는 동일한 논리의 반복이다. 세 번째로 강한 상대와 붙어서 우승하기 위해서는 그보다 강하거나 동등해야 한다. (req[3] >= 5)
다음 상대는 두 번째로 강한 사람이고, 세 번째 사람의 능력을 흡수했을 때 req[4] 이상이면 우승 가능하다.
req[3] = max(5, req[4]-5) = max(5, 6) = 6

 

방법 2 - greedy

이 방법 또한 방법 1에서의 다음 관찰을 바탕으로 한다.

어떤 사람 a가 우승할 수 있는지는 다음과 같은 greedy 방식으로 확인이 가능하다.
a가 능력치가 낮은 순으로 모든 상대와 대결했을 때 우승할 수 있으면 우승 가능하고 그렇지 않으면 우승 가능하지 않다.

좀 더 생각해보면 다음과 같은 관찰도 가능하다.
어떤 사람이 우승하면, 그보다 강한 상대는 모두 우승 가능하다.

우승할 수 있는 최소 능력의 사람을 binary search로 찾아주자.

 

 

F

풀이는 editorial 과 동일하기 때문에 풀이 논리 중 일부만 간략하게 정리하자.(binary search 부분 생략)

a	1	-3	4	2	-10	3
pref	1	-2	2	4	-6	-3

위와 같은 예시에 대해 drive가 t 시간 동안 회전할 때의 값 value[t]를 구해보자. 이때 n은 배열 a의 사이즈이며 위 예시에서는 6이다

i) t < n(=6)
value[t] = pref[t]

ii) n <= t < 2n
value[t] = (-3)*1 + pref[t mod n]

iii) 2n <= t < 3n
value[t] = (-3)*2 + pref[t mod n]

정리하면, t = nq + r where 0 <= r < n 에 대해
value[t] = Sq + pref[r] where S is sum of all value in array a.

어떤 값 x에 대해
value[t] >= x, i.e. Sq + pref[r] >= x 가 되는 최소 t를 찾자. 이 값이 최초로 drive가 멈추는 순간이다.

그 전에, 이러한 t가 없는 경우를 살펴보자.(무한히 도는 경우)
일단 한 바퀴를 돌기전에 dirve가 멈추면 안되므로 임의의 pref 값보다 x가 커야한다.
for every t, pref[r] < x. 이는 max(pref[r]) < x와 동치이다.

한 바퀴 돌고 난 후에도 drive는 멈추면 안되므로
for every t, S+pref[r] < x

두 바퀴 돌고 난 후에도 drive는 멈추면 안되므로
for every t, 2S+pref[r] < x

이때 좌변에 추가되는 S가 0이하라면 dirve가 무한히 돌아도 좌변이 항상 x보다 작다.
즉, (max(pref) < x 이고 S <= 0) 이면 drive는 무한히 돈다.

 

이제 dirve가 무한히 돌지 않는 조건(max(pref) >= x and S > 0)에서 어떤 값 x에 대해 최초로 drive가 멈추는 순간 t 를 찾자.

if: max(pref) >= x 이라면 디스크는 한 바퀴를 돌기 전에 멈출 것이다.
elif: max(pref) >= x - S 이라면 디스크는 한 바퀴를 돌고나서 멈출 것이다
elif: max(pref) >= x - 2S 이라면 디스크는 두 바퀴를 돌고나서 멈출 것이다
... 

Sq + pref[r] >= x
Sq >= x - max(pref)
q >= ceil(x - max(pref) / S) = (x - max(pref) + S - 1) // S

적어도 (x - max(pref) + S - 1) // S 만큼 회전하면 디스크는 멈춘다.