Codeforces #930 Div. 1

3줄 요약

1. A, B, C를 생각보다 빨리 풀었지만, 쓸데 없는 패널티 4개를 받아서 굉장히 안타까웠다.

2. 그럼에도 불구하고 레드 퍼포가 나왔고, 최대 레이팅 달성에 성공했다. ㅎㅎ

3. IOI 국대 선발고사 연습한게 효과가 좀 있는 듯 하다. ㅠㅠ

 

서론

2/29(목)에 오랜만에 Codeforces #930 시험에 응시했다.

본계정으로 시험을 보는 것은 작년 10월 이후에 처음이었다.

오랜만에 코포를 하는 것이기 때문에 낮에 옛날 코포 Div. 1 버추얼을 돌았다.

성적이 꽤나 잘 나왔고, 전보다 실력이 늘었음을 느낄 수 있었다.

시험이 시작되었다.

A

A 문제를 읽었다. 최댓값이 N-1보다 크거나 같은 최소의 (2^k-1)꼴 자연수가 될 것이라는 것을 알아냈고, 모든 N에 대해서 0<=x<N을 만족하는 자연수 x가 존재하여 N xor x가 답이 된다는 것을 알아냈다. 문제에 주어진 연산을 사용할 방법을 요리조리 고민해보다가, 문득 a, b, c, d가 서로 달라야 한다는 조건이 없다는 것을 알아냈다. 그래서 a=b, c=d로 놓으면 (N-1)번의 연산으로 최댓값을 알아낼 수 있었다. 최댓값을 찾은 다음은 크게 어렵지 않았다. N-1을 찾았기 때문에 이와 xor을 했을 때 답이 나오는 원소들을 모두 찾을 수 있고, 그 중 최소를 찾으면 답이라는 사실을 알 수 있다. 바로 구현해서 제출했는데, 틀려서 매우 당황했다. 알고 보니 단순 구현 실수였고, 멍청한 실수를 한 번 더 한 다음에서야 겨우 AC를 받을 수 있었다.

B

B 문제를 읽었다. 읽자마자 공이 어떻게 움직일지는 정성적으로 예측할 수 있었지만, 값을 구하는건 좀 귀찮게 생겼다. 그래도 4개의 대칭적인 케이스로 나눠서 구현하기 시작했고, 각각의 케이스를 구현할 때 매우 무서웠지만, 다행히 바로 답이 나왔다. 예제가 맞으면 답이 틀리기 쉽지 않을 것 같아서 바로 제출했고, 별다른 어려움 없이(?) AC를 받을 수 있었다.

 

지금까지 A에서 패널티 2스택을 성실하게 쌓았기 때문에 C 문제를 무조건 풀어야만 한다고 생각했다.

C

C 문제를 읽었다. 뭔가 대충 적당히 자료구조를 살짝 곁들인 DP를 사용하면 해결할 수 있을 것 같았다. 일단 포켓몬 k에서 i로 전이가 되었고, j번 능력치를 사용해서 넘겼다고 생각하면, j번 능력치를 바로 연속해서 또 사용할 필요가 없다는 사실을 먼저 관찰했다. (같은 능력치를 두 번 연속 쓸 바에는 차라리 중간 포켓몬을 사용하지 않는 것이 훨씬 이득이다.) 따라서 DP_i, j="현재 i번 포켓몬이 무대(?)에 서있고, 이 포켓몬은 j번 능력치를 통해서 온 것일 때, 최소 비용"이라고 정의하자. 그러면 DP_i, j=Min(DP_x, k + Max(A_x, j-A_i, j, 0)) (단, x<i, k!=j) 로 전이 식을 간단하게 세울 수 있다. 이를 무지성으로 구현하면 O(N^2M^2)이 뜨지만, 자료구조에 살짝 데치면 O(NMlogN)으로 줄일 수 있다. 우선 M항을 하나 줄일 수 있는데, 위 식에서 k를 러닝할 필요 없이, 왼쪽에서부터 최솟값, 오른쪽에서부터 최솟값 배열을 관리하면 된다. 이제 N을 logN으로 바꾸면 문제가 풀린다. 위 식을 자세히 처다보면, 계산하기 가장 까다로운 부분은 Max(A_x-A_j, 0)이라는 것을 알 수 있고, 따라서 A_x<A_j인 x와 A_x>=A_j인 x로 분리해서 푸는 것이 훨씬 간단하다는 것을 알 수 있다. 식을 적당히 정리하면, A_i, j를 열별로 압축해서 최솟값 세그먼트 트리를 M개 들고 있으면 문제가 풀린다. 풀이를 알아내자마자 매우 빠르게 구현에 들어갔고, 15분만에 초안 코드가 완성되었다. 예제는 나왔는데 제출하니까 WA. 한참 씨름하다가 얼탱이 없는 실수를 발견하고 제출하니까 또 WA. (tmp=x+y;라고 써야 하지만 x+y;로 썼다..) 또 실수를 발견하고 제출하니까 그제서야 AC가 나오고 말았던 것이다.(이번에는 줄바꿈 이슈였다;;)

* 여담이지만 C문제를 세그먼트 트리로 푼 사람은 거의 없었다. 다들 PQ 써서 푼 것 같은데 잘 모르겠다.

 

이렇게 C까지 풀고 나니까 30분 정도 남았고, 더이상 풀 수 있는게 없었다.

결과

C를 풀었을 때만 해도 2500점대 퍼포먼스가 나왔는데, 꾸준히 누적한 패널티로 인해 등수가 점점 밀렸고, 나보다 훨씬 늦게 C를 푼 사람보다도 등수가 엄청 밀리는 슬픈 현상이 벌어지고 말았다. 최종 퍼포먼스는 2442로, 그래도 매우 만족스러운 결과라고 생각한다.

여담

1. 끝나고 나서 D를 읽어봤는데, 재밌어 보인다. 대충 투 포인터를 쓸 것처럼 생겼다. 시간 나면 업솔빙을 해야겠다.

2. Div. 2를 구경해봤는데, C까지 푸니까 대충 2600점대 퍼포가 뜬다 0o0 확실히 점수 올리기는 딥2가 훨씬 쉽고 행복한 것 같다.

3. 코포 오랜만에 했는데 재밌다. 또 해야지.... 라고 생각했으나 딥1 코포는 달에 2~3번 있다는 사실을 알고 안타까웠다.

4. 대회가 끝나고 한참 뒤 B 문제가 옛날 문제와 겹친다는 소문을 듣고 찾아보았다. 당시에는 <, > 대신 U, D로 표현되었다.