Codeforces #1012 Div.1

3줄 요약

1. A, B1, B2, C1을 풀었다.

2. 2850 퍼포가 나왔고, 레드를 가며 최대 레이팅 달성에 성공했다.

3. 문제를 안 푼지 시간이 좀 되었는데, 꽤나 높은 퍼포먼스가 나와서 좋았다.

서론

3/23(일)에 Codeforces #1012 시험에 응시했다.

전날에 버추얼을 돌았는데, 찐레드 퍼포가 나와서 이번 코포도 기대할만 하다고 생각했다.

시험이 시작되었다.

A(~0:05)

A 문제를 읽었다.

대충 n/2에 가장 가까운 소수 p를 잡고 p, p-1, p+1, p-2, p+2, ...을 출력하면 되는 문제였다.

바로 맞았다.

B1(~0:15)

B1 문제를 읽었다.

B[i]-A[i]의 누적합을 만들어서 적당히 스택으로 처리해줄 수 있었다.

바로 맞았다.

B2(~0:45)

B2 문제를 읽었다.

B1 문제와 비슷하게 하되, 파라메트릭 서치를 하면 될 것 같았다.

오랫동안 생각해보니 그냥 그리디하게 가중치의 합을 하면 된다는 것을 알게 되었고, 바로 구현했다.

그런데 쓸데 없는 경우를 처리하지 않아서 한 번 틀리고 맞았다. 이 때까지만 해도 스노우볼이 어디까지 굴러갈지 예상하지 못했다.

C1(~1:24)

C1 문제를 읽었다.

DP를 적당히 정의해서 기댓값을 구하면 되는 문제였다.

O(n^2l)로 구현해도 맞는 문제였지만, 잘못 생각해서 누적합으로 O(nl)로 구현했다.

바로 맞았다.

결과

C1 문제를 풀었을 당시 19등이었는데, C2와 D를 풀지 못해 등수가 계속 떨어져 41등으로 마무리했다.

B2에서 패널티를 받은 것이 정말 아쉽다.

그래도 최종 퍼포먼스는 2850으로, 상당히 만족스럽다.

여담

1. C2 푼 사람들이 꽤나 많아서 C2를 업솔빙해야겠다.

2. 평소와 시간대가 달라서 응시자 인원이 적은 라운드였다.

3. 인생 최초로 레드를 가게 되었다. ^오^