Codeforces IM 달성 (부제: 점수의 무의미함)

처음 오렌지를 찍고 1년 2개월이 지난 후, 드디어 International Master(찐렌지)에 도달했습니다. 하지만 이 과정이 일반적이지 않고 너무나도 기묘했기 때문에 글으로 기록해보려 합니다. 찐렌지에 도달한 라운드는 한국 시간 기준 화요일 밤에 있었는데, 토~화 4일동안 친 코드포스 3개와 앳코더 2개 라운드에 대한 후기와 전체적인 소감을 다룰 예정입니다. 카테고리는 애매했는데 그냥 CP로 두기로 했습니다.

 

2/25 (토) 21:00 - AtCoder Regular Contest 157

 

 

 

A. XXYYX (0:10, +4) *348

생각을 대충 하고 넘어갔더니 A번에서 4번 틀리고 10분이 걸렸습니다. 문제 자체는 쉽습니다.

 

B. XYYYX (1:06, +8) *1529

라운드를 망친 원흉입니다. 우선, 처음에는 문제를 잘못 읽었습니다. 이게 크게 다가온 이유는, 잘못 읽은 버전도 예제가 다 나왔기 때문입니다. 잘못 읽었다는 사실을 발견했을 때에는 이미 30분이 넘는 시간과 4번 정도의 WA를 적립한 상태였습니다. 그 이후에도 몇 번 더 틀린 후 AC를 받았습니다.

 

C. YY Sqaure (upsolved, +) *1802

재미있는 문제입니다. DP를 이용합시다. \(DP[i][j] = C_0 \times 0 + C_1 \times 1 + C_2 \times 4 \cdots\)라 하면, 누적합을 2번 적용해 DP를 전이시켜줄 수 있습니다. 누적합을 한 번 적용하면 1, 4, 9.. 가 1, 3, 5.. 가 되고, 여기서 한 번 더 적용하면 2, 2, 2.. 가 되기 때문입니다. 풀이 자체는 빨리 찾았지만, B에서 멘탈이 나가있었기 때문에 구현 속도가 늦어 대회 종료 10분 정도 후에 해결했습니다.

 

후기

A, B 모두 못하는 유형의 문제가 나왔습니다. C는 충분히 풀 만한 문제였지만 시간 부족으로 풀지 못했고, 결과론적이지만 C를 풀었다면 옐로도 유지하고, 후술한 참사도 없었을 것 같습니다. 별개로 페널티 60분은 좀 혼나야 합니다.

 

2/25 (토) 23:20 - Codeforces Round #853 (Div. 2)

 

 

A. Serval and Mocha's Array (0:02, +)

gcd는 단조감소하고 배열의 길이는 증가하므로 배열의 길이가 2일 때에만 조건을 만족시켜주면 됩니다. 

 

B. Serval and Inversion Magic (0:07, +1)

양 끝부터 확인하면서 바꿔야 하는 구간이 1개인지 확인해주면 됩니다. 이런 유형을 코포에서도 꽤 많이 보고 퍼솔을 먹었던 지난 리저널 I도 이런 문제였기에 비교적 빨리 풀었습니다.

 

C. Serval and Toxel's Array (0:18, +)

각 숫자가 등장하는 시간을 모두 구하고 더블 카운팅의 원리를 적용해 전체 횟수에서 잘 빼주면 됩니다. 문제 상황이 작위적이라 별로 마음에 들진 않았습니다.

 

D. Serval and Shift-Shift-Shift (upsolved, -7)

애드혹 구성적 문제입니다. 저는 풀이를 꽤 빨리 찾았으나, 굉장히 찾기 힘든 부분에 구현 실수가 있어 1시간 동안 같은 코드만 보다 대회가 끝났습니다. 대회 종료 후 스트레스 테스트를 돌려 실수를 고쳐 내 맞았습니다. 제 풀이는 복잡하고 정해도 아닌 것 같아 생략하도록 하겠습니다.

 

후기

앞에 있던 앳코더와 더불어 멘탈이 제대로 갈렸습니다. D가 꽤 어려워서 퍼포는 2000점 정도로 꽤 높게 나왔습니다. 다행인 점은 언레였다는 것입니다. 과연 뒤에 있을 레이티드 대회는 잘 쳤을까요..?

 

2/26 (일) 21:00 - AtCoder Beginner Contest 291 (Sponsored by TOYOTA SYSTEMS)

 

 

A. camel Case (0:01, +) *8

하면 됩니다.

 

B. Trimmed Mean (0:03, +) *32

지문이 좀 복잡하긴 한데, 하면 됩니다.

 

C. LRUD Instruction (0:06, +) *188

map을 써서 잘 하면 됩니다.

 

D. Flip Cards (0:09, +) *720

전형적인 상태 \(2N\)개 DP입니다.

 

E. Find Permutation (upsolved, -2) *1069

여기서 멘탈이 나갔습니다. 문제는 그냥 "위상정렬을 해라" 정도의 문제입니다. 과연 제가 정말 위상정렬을 못할까요? 저는 그렇게 생각하지 않습니다. 다만 너무 당연히 써 오던 사이클 판별 코드가 사실 틀린 것이었고, 저는 그걸 알아채지 못했을 뿐입니다. 어리석게도 여기서 1시간 가량을 날렸습니다. 사실 평소의 앳코더였다면 뭐 조금 억울하고 말겠지만, 이 날은 평소와는 달랐고.. 이는 큰 재앙을 초래합니다.

 

F. Telepoter and Closed off (1:00, +) *1449

E를 거르고 간 F는 쉬웠습니다. 이런 식의 양방향 BFS, 숫자 장난질 모두 앳코더에 많이 나오는 유형이라 보자마자 풀었습니다.

 

G. OR Sum (upsolved) *2176

그리고 옆에 있던 qjatn0120 선배가 G를 풀었길래 보러 갔습니다. G는 이리 보고 저리 봐도 FFT였습니다. 뭐 조금의 테크닉이 필요하긴 했지만, 크게 어렵진 않았습니다. 바로 백준에 가서 FFT 코드를 가지고 왔고, 5분 정도 코딩을 해 정해 코드를 완성했습니다. 하지만 예제가 나오지 않았습니다. 어딜 봐도 틀린 점이 없었기 때문에 저는 영문도 모른 채 그대로 대회가 끝났습니다. 그리고 발견한 오류는 다음과 같습니다.

정말 멋지다.

Ex. Balanced Tree (upsolved) *2097

이 셋의 화룡점정인 Ex입니다. ABC의 Ex번 난이도는 보통 굉장히 어렵습니다. 항상 최소 오렌지(2400 이상)이었으며, 동메달/은메달의 출현 빈도도 상당했습니다. 하지만 옆에 있던 qjatn0120 선배과 menborong님이 Ex를 풀었다 했을 때 깨달았어야 합니다. 이 셋은 뭔가 달랐다는 것을.. 요약하자면, Ex는 G보다도 쉬웠습니다. 그냥 센트로이드 트리를 만들면 됩니다. 놀랍게도 이게 그냥 정해이며, 이를 숨기기 위한 별도의 장치도 없었습니다. 대회 끝나고 백준에 있던 코드를 가져와 AC 코드로 만드는 데에 5분도 채 걸리지 않았습니다.

 

후기

뭐 못 푼 것은 제 잘못이 맞긴 하지만, 그걸 감안해도 셋이 너무 역대급으로 별로였습니다. 특히 Ex는 백준 대회에 저렇게 나오면 욕을 엄청 먹을 것이라는 생각이 들었습니다. 역시 ABC에 기업 이름이 붙어 있으면 거르는게 맞습니다.

 

2/27 (월) 23:35 - Codeforces Round #854 by cybercats (Div. 1 + Div. 2)

 

 

A. Recent Actions (0:07, +)

A번 치고 굉장히 어려웠습니다. 평소 B에 버금가는 수준이었다고 생각합니다. 보통 A번 정도는 \(O(N)\) 풀이가 있더라도 \(N\)을 100 정도로 작게 주는 경우가 많은데, 이 문제는 그렇지도 않았습니다.

 

B. Equalize by Divide (0:29, -2)

역시 B번 치고 굉장히 어려웠습니다. 1이 하나라도 있으면 모든 수가 1이 아닌 이상 불가능하고, 아니면 항상 가능합니다. 최솟값을 잡아 다른 수를 최솟값 이하가 될 때까지 계속 나누는 것을 반복하면 됩니다. 나누는 수가 항상 2 이상이기 때문에 횟수는 보장되는데, 저는 횟수를 적게 돌렸더니 main test에서 틀렸습니다. 솔직히 이 정도는 pretest에서 잡아야 하지 않나 싶었습니다.

 

C. Double Lexicographically Minimum (0:59, +1)

전형적인 코포식 문제입니다. 예제가 나름 친절해서 규칙 찾는 데에 오래 걸리지는 않았지만, 그냥 문제가 별로라 화가 좀 났습니다. 

 

D1. D2. Hot Start Up (1:49, 2:09, +, +1)

경찰차와 비슷한 유형의 DP입니다. 저는 이미 앞에서 상당히 망했기에 고점을 노리고 D2를 먼저 보았습니다. 그리고 이번 라운드의 패착이 되었습니다. 꽤 오래 생각했는데도 별 다른 해법이 나오지 않아 D1를 먼저 풀었는데, D1에 레이지를 박으면 바로 풀이가 나와 D2도 풀었습니다. D1을 먼저 잡았다면 E를 풀 시간도 남았을 것 같아 아쉽습니다.

 

후기

B가 안 터진 기준으로 오렌지를 가까스로 유지하는 퍼포먼스였는데, B가 시원하게 터지면서 퍼플로 가게 되었습니다. 그리고 이는 다음 라운드에서 크나큰 스노우볼로 돌아오게 됩니다..

 

2/28 (화) 23:35 - Educational Codeforces Round 144 (Rated for Div. 2)

 

ㅋㅋㅋㅋㅋㅋ

A. Typical Interview Problem (0:04, +)

길이가 20 이상인 예시 문자열을 하나 만들고 나이브하게 비교해주면 됩니다. 20 미만으로 만들었다 한 번 틀렸습니다.

 

B. Asterisk-Minor Template (0:09, +)

a*, *a, *ab* 중 하나가 최적입니다. 제한이 작기에 나이브하게 판별해주면 됩니다.

 

C. Minimum Set (0:20, +)

\(l\)에서 시작해서 2를 계속 곱한 것이 집합의 최적 형태입니다. 따라서 집합의 최대 크기는 쉽게 구해줄 수 있습니다. 여기서, 2 하나를 3으로 바꿔줄 수 있습니다. 4 이상은 2를 2개 쓰는 것이 더 효율적이라 불가능하며, 3을 2개 쓰는 것 역시 2를 3개 쓰는 것이 더 효율적입니다. 두 경우 모두 쉬운 수학으로 \(O(1)\)에 구해줄 수 있습니다. 관찰을 빨리 해 굉장히 빨리 풀었고, 이 문제를 풀었을 때 누텔라 퍼포가 나와서 기분이 좋았습니다.

 

D. Maximum Subarray (0:45, +3)

최대 연속 부분합을 구하는 Kadane DP를 변형하면 됩니다. \(dp[i][j] = \) \(i\)번째 수까지 \(j\)번의 찬스를 써 만들 수 있는 끝을 \(i\)번째 수로 하는 최대 부분합으로 정의하면 DP 전이는 비교적 쉽습니다. 답을 잘 구해주어야 하는데, \(j=k\)가 아닌 곳에서도 답이 나올 수 있음에 유의하면 됩니다. D까지 풀고 난 후의 퍼포는 2800 정도였습니다.

 

E. Colored Subgraph (1:38, +)

처음에 보고 굉장히 어렵다고 생각했지만, 제가 비교적 자신있는 트리 문제여서 계속 잡아봤습니다. 루트가 고정되어 있다고 생각하면, 간단한 트리 DP로 가능합니다. 각 정점에서, 자식들 중 가장 짧은 길이의 chain을 이어주는 것이 최적입니다. 그러면 각 정점은 자식의 리턴값이 담긴 set을 하나씩 가지고, set의 최솟값+1을 계속 전달하는 형태입니다. 체인이 끊기는 지점은 각 set의 2번째로 작은 값, 또는 루트 set의 최솟값+1이기에 이들 중 최솟값을 구해주면 됩니다.

이를 모든 \(r\)에 대해 구해줄 수 있습니다. 루트의 set과 자식의 set을 업데이트 해 자식을 루트로 옮기는 것은 \(O(logN)\)에 가능하며, 초기에 임의의 정점에 대해 dfs를 수행해 set을 모두 구해준 후 다시 추가적인 dfs로 set을 업데이트 하며 각 정점이 루트일 경우의 정답을 구해줄 수 있습니다. 쉽게 쓰긴 했지만 굉장히 어렵고 좋은 문제라고 생각합니다. 제가 잘 풀어서 그런건 아니고요.. 백준에 있었으면 추천! 과 다이아 4~5정도의 난이도를 주었을 텐데 아쉽습니다.

 

후기

솔직히 말하자면, 에듀 라운드를 굉장히 잘 치는 편이라 오렌지에 가지 못할 걱정은 거의 없었습니다. 이번 라운드 종료를 기준으로 최근 제 rated 에듀 라운드 전적은 아래와 같습니다.

에듀의 재앙

D를 푼 시점에서 오렌지 복귀는 확정이었지만, 그럼에도 불구하고 E 제출이 돌아가는 동안 심장이 정말 빨리 뛰었습니다. 대회의 경중을 떠나, 어렵다고 생각되는 문제를 자력으로 풀 때가 PS하며 가장 뿌듯한 순간이지 않나 싶습니다. E를 푼 후의 순위를 확인해보니 전체 30등, rated 참가자 기준 3등이었습니다. 그 전날 퍼플로 떨어졌던 것이 정말 미친듯이 고마웠습니다. 에듀라 레이팅 반영이 늦게 되었는데, 거의 10분에 한 번은 계속 확인했던 것 같습니다. 다행히 오늘 아침에 레이팅이 잘 들어왔고, 200점 정도 오를 것을 예상했는데 230점이 올라 퍼플에서 한 번에 IM을 찍었습니다. 제출 1번만 덜 했으면 2등에 누텔라 퍼포인데.. 약간 아쉽습니다ㅋㅋ

 

전체 후기

 

제가 위에서 친 라운드의 퍼포먼스는 코드포스 기준으로 블루-퍼플-블루-블루-2900점(...) 입니다. 그렇다면 제 실력은 블루, 퍼플, 2900점(...) 중 하나일까요? 일단 제 생각에 그렇지는 않은 것 같습니다. 그렇다면 지금 점수인 2300점은 제 실력을 잘 나타내는 숫자일까요? 그것도 잘 모르겠습니다. 앞의 네 라운드를 칠 때에는 요새 공부를 소홀히 했나.. 그냥 실력이 죽었나.. 와 같은 오만가지 생각이 다 들었지만, 마지막 라운드 후에는 그냥 레이팅이 얼마나 덧없는 것인지 다시 한번 느낄 수 있었습니다. 코드포스를 비롯해 solved.ac 레이팅, 백준 해결 문제수는 실력을 정확히 나타내는 지표라 할 수 있을까요? 더 나아가, 수상 실적은 실력을 정확히 나타내줄까요? 다 어느 정도 그럴싸한 지표이지만 어느 것도 실력을 정확히 나타내지는 않습니다. 어느 좋은 글의 표현을 빌리자면, 이런 것들은 모두 실력의 샘플링이기 때문이니까요. 그렇다면 실력이란 무엇일까요? 제 생각에는 각자가 생각하기 나름인 것 같습니다. 내가 생각하는 나의 수준이 바로 실력이 아닐까요? 그러기 위해서는 자신의 수준을 객관적으로 판단하기 위한 노력이 필요합니다. 모르는 것이 무엇인지 모르는 것이 가장 무섭다는 말도 있듯이, 자신의 실력을 잘 알고 공부하는 것만큼 좋은 공부법은 없다고 생각합니다. 점수에 너무 연연하지 않고 본인이 만족할 수 있는 PS를 할 수 있는 PS러들이 되면 좋겠습니다. 물론 저는 레드 가면 박제하고 부캐로 돌릴 생각입니다