Codeforces Round 880 (Div. 1)

Dashboard - Codeforces Round 880 (Div. 1) - Codeforces

A - k-th equality

brute force

00:10 AC

 

B - Lottery (not solved)

우선 x를 선택하였을 때 이기는 경우의 수 f(x)를 구해보자.

x를 선택한 사람이 k명 이상이라면 f(x) = 0이 된다.

그렇지 않다면 다음과 같이 계산할 수 있다.

 

N명의 사람이 선택한 수 중 x보다 크지 않고 x에서 k번째로 가까운 값을 c라고 하자.

마찬가지로 x보다 작지 않고 x에서 k번째로 가까운 값을 d라고 하자.

내가 당첨되기 위해서는 당첨 번호가 c 또는 d보다 x에 더 근접해야 한다.

이를 이용하여 당첨 구간 [s, e]를 구할 수 있고 f(x) = e - s + 1이 된다.

s와 e는 다음과 같다.

• s = x - (x - c - 1) / 2;
• e = x + (d - x - 1) / 2;

c나 d가 존재하지 않는 경우도 있는데 이때는 끝값을 잡으면 된다.

다음과 같이 s와 e를 재정의할 수 있다.

• s = c가 존재 ? x - (x - c - 1) / 2 : 0;
• e = d가 존재 ? x + (d - x - 1) / 2 : M;

이제 x를 선택하였을 때 이기는 경우의 수 f(x)를 구할 수 있다.

하지만 M 제한이 크기 때문에 brute force는 불가능하다.

 

N명의 사람들이 선택한 수를 정렬한 배열을 A라고 하자.

이때 아래의 각 구간에 대해서는 당첨 구간 [s, e]가 동일함을 알 수 있다.

• [A[i], A[i]]
• [A[i] + 1, A[i + 1] - 1]
• [0, A[0] - 1]
• [A[N - 1] + 1, M]

위의 각 구간을 [l, r]이라고 하자.

 

c와 d의 존재 여부에 따라서 f(x)는 다음과 같이 계산된다.

• c와 d 모두 존재 -> (x - c - 1) / 2 + (d - x - 1) / 2
• d만 존재 -> x + (d - x - 1) / 2
• c만 존재 -> M - x + (x - c - 1) / 2
• c와 d 모두 존재하지 않음 -> M + 1

각 경우에 대하여 조금 더 자세히 관찰해보자.

 

1. c와 d 모두 존재

이 경우 c와 d의 parity에 따라서 구간의 f(x)는 모두 동일하거나 1만큼 커졌다 작아졌다를 반복한다.

따라서 l과 (l + 1)만 검사해도 된다.

 

2. d만 존재

이 경우 x를 최대화하는 것이 이득이므로 r만 검사해도 된다.

하지만 d의 parity에 따라서 f(r) = f(r - 1)일 수도 있으므로 (r - 1)도 검사해야 한다.

 

3. c만 존재 또는 c와 d 모두 존재하지 않음

이 경우 x를 최소화하는 것이 이득이므로 l만 검사해도 된다.

f(l) = f(l + 1)일 수도 있지만 문제의 조건에 따라서 l만 검사하면 된다.

 

이제 답의 후보를 O(N)개로 줄일 수 있다.

각 후보 x에 대하여 f(x)는 O(1) 또는 O(log N)에 구할 수 있다.

위의 논리를 약간 복잡한 case work로 구현하면 된다.

 

여기까지만 하면 WA를 받는데 예외 case가 있기 때문이다.

0을 항상 검사해야 하는데 이유는 직접 생각해보기를 바란다.

이제 AC를 받을 수 있다.

 

하지만 이렇게 구현하면 코드가 상당히 복잡해진다.

조금 불필요하지만 l, (l + 1), (r - 1), r을 모두 검사하도록 구현해도 된다.

이렇게 해도 답의 후보는 O(N)개이고 시간은 조금 더 소요되겠지만 구현이 많이 간편해진다.

 

여기서 구간의 모양까지 생각하면 A[i] + (-2 to 2)와 0만 검사하도록 구현해도 됨을 알 수 있다.

이렇게 하면 답의 후보는 정확히 최대 (5 * N + 1)개가 되며 구현은 훨씬 간편해진다.

 

C - Twin Clusters (not solved)

Pass

 

D - Doctor's Brown Hypothesis (not solved)

Pass

 

E - Old Mobile (not solved)

Pass

 

F - Good Graph (not solved)

Pass

 

끝

끝