Codeforces Round 880 (Div. 1)

https://codeforces.com/contest/1835

아 화가 난다.

이건 무조건 레드 간건데...

이 셋은 좀 똥이라고 생각한다.

 

A. K-th equality

 

문제에서 A, B, C가 3보다 큰 경우가 5개밖에 없다고 한다. (일단 이 조건도 좀 똥같다)

따라서 pow(10, A) 정도의 복잡도로 그냥 모든 a에 대해서 확인해주면 된다.

적당한 a에 대해서 문제의 조건 (A, B, C)의 조건을 만족하는 b, c는 O(1)에 확인해줄 수 있다.

그래서 그냥 모든 a에 대해서 순회하면서 딱 k번째를 만족하는 a가 나오면 k번째 b를 선택하면 된다.

 

B. Lottery

 

일단 첫째로 도대체 왜 a를 정렬해서 주지 않았는지 이해가 되지 않는다.

그리고 두 번째로 왜 예제에 같은 표를 두 번 이상 사는 것을 박아놓지 않았는지 이해를 할 수 없다.

마치 0~m 중에서 표를 하나씩 뽑았다는 느낌이 들어서 꽤 오랜 시간 같은 표를 두 번 이상 사는 것을 고려하지 않았다.

-> 이것은 나중에 왜 n과 m에 대한 크기 조건이 없는지에서 깨닫게 되었다.

이와 별개로 "ticket belonging to the person with a smaller index is declared a winner."라는 표현이 있다.

나는 처음에 동일 표를 두 병이 살 수 없기에, target이 3이라면 1번 티켓이 5번 티켓에 비교우위라는 뜻으로 알았다.

하... 아무튼 훨씬 더 잘 설명할 수 있었으텐데 

 

아무튼 직관이 다음과 같다.

적당히 a[i] +- 2 범위 내에 무조건 답이 있다.

a[i]와 a[i + 1] 사이에 답이 있다고 가정하자.

그렇다면 왼쪽 범위는 (x + a[i - k + 1] + 2) / 2, 오른쪽 범위는 (x + a[i + k] + 2) / 2이다.

딱봐도 양쪽 범위의 차는 상수값이다. (x에 관계없에 a[i - k + 1], a[i + k]에 의해 결정된다.)

그래서 답은 웬만하면 a[i] + 1, a[i] + 2이다.

만일 i - k + 1 < 0 이거나 i + k >= n인 상황을 고려해보면 a[i + 1] - 1, a[i + 1] - 2도 답이 될 수 있음을 확인할 수 있다.

이제 추가로 x = a[i]인 상황들을 모두 확인해보면 된다.

 

C. Twin Clusters

 

이거는 보자마자 랜덤을 박는게 맞았다.

B에서 멘탈적으로 충격을 박고 판단력이 흐려져셔 랜덤을 박지 않았다

코포의 법칙 중 하나) 만일 예제에 -1이 없으면 -1인 경우는 없을 것이다.

.

일단 이 문제는 Four XOR처럼 문제가 바뀐다. (psum[a] ^ psum[b] ^ psum[c] ^ psum[d] = 0인 a, b, c, d를 찾아라)

이때 psum[a] ^ psum[b]의 쌍의 개수는 대충 2^(k * 2 + 1)이고, 가능한 숫자의 개수는 2^(k * 2)이다.

따라서 비둘기집에 의해서 답은 무조건 존재한다.

아니 이게 대충 생각하면 겨우 2배라서 답을 잘 찾지 못할 거 같아서 랜덤을 제쳤다.

사실 2배인거에 관계없이 가능한 숫자의 개수가 2^34개라는 점에서 벌써 랜덤풀이가 가능하다.

(1 - 1/x) * (1 - 2/x) * (1 - 3/x) * .. * (1 - 1e6 / x)를 계산해보면 매우 높은 확률로 답을 구할 수 있음을 알 수 있다.

 

Deterministic인 풀이도 존재한다.