CF Master(오렌지) 달성 후기 + PS 회고록 + Educational Codeforces Round 186 (Rated for Div. 2) 후기

서론

연말 코드포스 라운드 몇 개를 잘 쳐서 운 좋게 오렌지를 달성하게 되었습니다. 여태까지 살아오면서 이렇게 cp를 열심히 한 적이 없었던 것 같은데, 성과가 안 나와서 초조했었는데 운 좋게 성과가 나오게 되었습니다.

PS 회고

저는 중학교 1학년 때 c++과 ps를 학원에 다니면서 처음 접하게 되면서 학원 OJ 사이트에서 문제를 풀고 공부하면서부터 ps를 시작하게 되었습니다. 중학교 2학년 때 KOI에서는 1차에서도 상을 받지 못하는 고배를 마셨지만, 운 좋게 중학교 3학년 때 중등부 1차 동상, 2차 은상이라는 제 실력을 넘어서는 상을 받게 되었습니다. 영재학교 원서 접수 일주일 전까지도 영재학교의 존재도 몰랐다가 학원에 같이 다니는 친구가 KSA에 정말 가고 싶다고 지원해본다고 하였는데, 저도 당시 과학고등학교에 진학하는 것을 지망하고 있었고, 그래서 함께 지원하게 되었습니다.

Ps 지식과 자신감으로 가득하던 저는 2차 문제들을 ps적 관점에서 접근해서 풀어내며 운 좋게 2차 시험을 잘 치게 되어 KSA에 최종 합격하게 되었습니다. 막상 가서는 ps를 열심히 하지는 않았던 것 같습니다. IOI 계절학교도 지원해서 붙었었는데, 하필 학교 성적이 저조해서 계절학기를 들어야 했던 바람에 좀 고생을 많이 했습니다. IOI 처음반에서는 zoom 수업을 통해서 조교님들이 과제를 내주고, 그걸 5시간 정도 푼 다음, 서로 풀이를 토의하는 시간을 가졌는데, 여름학교까지만 해도 그래도 꽤 되는 친구들이 문제를 풀려고 노력은 했었는데 겨울학교에 가니 맨날 푸는 친구들만 문제를 풀고 나머지 친구들은 zoom을 틀어만 놓고 놀았습니다.

저는 필수문제 1~2문제 정도만 풀고 노는편이었고, 생각해보면 그런 좋은 교육을 무상으로 받을 수 있는 기회였는데 어느 정도 날리기도 했던 것 같습니다. 당연히 선발고사 날에는 밤낮까지 바뀌어서 고생을 했는데, 첫째 날에는 AC코드라고 생각했던 코드가 섭테 20번대 후반에서 터져버려서 대체 어디서 틀린건지 디버깅만 하다 찾지 못해서 망했고, 둘째 날에는 그냥 자버려서 시험 응시조차 안 하는.. 멋진 경험을 했습니다.

APIO도 나갔었는데, 그냥 저냥 제 실력에 비해서는 꽤 잘 본 것 같습니다. B번 30점 섭테가 굉장히 쉬운 골드 하위급 구현이어서 짰고, C번도 플 하위급 관찰을 하면 91점 정도를 받을 수 있어 그걸 긁은 다음 A번이 뭔 소린지 이해를 못해서 못 짰던 기억이 납니다. 선발고사를 망친 덕분에 당연히 계속반에는 못 갔고, 나중에 보니 처음반에서 맨날 문제 다 풀고 토의하던 고수분들은 국대가 되어 계시더군요.

학교 수업을 안 듣고 딴 짓하거나 백준하거나 둘 중 하나를 해서 티어를 꽤 올렸습니다. 아마 codeforces에 본격적으로 입문하기 전인 2학년쯤에도 다이아 정도의 티어를 찍었던 걸로 기억합니다. 그러다가 flakepowders 가 꼬셔서.. codeforces에 입문하게 되었습니다. 몇 판 정도를 잘 쳐서 블루 상위를 한 번 기록한 이후, 블루에서 쭉 진동했던 걸로 기억합니다. PS보다는 시험기간에는 벼락치기하고, 평소에는 놀고를 반복했던 것 같습니다.

Nypc도 몇 번 참여했었는데, 1학년 때에는 2-A에서 남들 다 푸는 검은 점 하얀 점 연결 dp를 당연히 알 리가 없었기 때문에 그걸 부분점수도 못 긁었고, 1번은 상당히 쉬운 골드급 문제여서 풀었던 걸로 기억합니다. 3번이 드론이었던 걸로 기억하는데, 답과 경로 역추적에 반반 점수가 걸려있는 문제였습니다. 시간이 모자라서 미쳐 코드를 다 못 짜서 역추적 코드를 못 짜고, 답 점수만 받아 50점을 받았는데, 좀 더 열심히 했으면 구현도 다 마치고, 2번 문제에서 부분 점수를 받아 본선에 한 번 더 가지 않았을까 싶습니다. 2, 3학년 때에는 그래도 짬이 있어서인지 어떻게든 추합권 안에 들어 본선에 갔다왔습니다. 2023년에 참가상으로 키보드를 안 줘서 상당히 실망했었는데, 다행히 2024에는 키보드를 줘서 아직까지 잘 쓰고 있습니다.

Codeforces를 안 해서 대회 출제 조건을 만족 못 하는 바람에 KSAAC 출제도 계속 유기했었는데, 블루를 몇 판 해서 찍어서 마지막 학기에는 참여할 수 있게 되었습니다. 지금 생각해보면 너무 자료구조 위주의 문제만을 내서 셋이 특정 사람들에게 유리한 셋이 된 것 같아 아쉽습니다. 그 사이에 cenix820 이 카이스트 프로그래밍 기초 과목 학점 인정 시험을 준비한다길래 jakekim0105, loreips, davidkim0 이랑 열심히 갈궜습니다. 다들 열심히 ps, cp를 안 접고 어느 정도 성과를 이루어 상당히 뿌듯합니다.

대학 입시도 열심히 놀았기 때문에 성공할 수 없었고, 한양대학교에 진학하게 되었습니다. 학기 초에 mathtw1030, lion0625 랑 팀을 짜서 UCPC, ICPC 팀을 미리 확정 짓고, 팀연습은 제가 유기를 많이 했습니다. UCPC는 거의 막차를 타서 본선을 나가는데 성공한 덕분에 본선에서 꽤 많은 것들 것 받아오고, 재밌게 칠 수 있었습니다. 이때까지만 해도 자신만만했는데, 열심히 하게 된 계기는 SCPC 본선을 못간게 컸습니다. 하루종일 문제를 풀었는데 남들이 다 긁는 5번 부분점수를 flush를 너무 많이 하는 바람에… 시간 초과를 받아서 못 긁게 되었고, 이로 인해서 본선 커트라인에 아슬아슬하게 걸려서 갔다 올 수 있었던 것을 못 가게 되었습니다.

CF 입문

그 이후로 제 실력에 부족함을 많이 느꼈고, 어떻게 연습할까 고민하던 와중 cywohoy님의 버추얼 같이 도는 방이 보였고, 버추얼을 함께 많이 돌게 되었습니다. 이때부터 그래도 0.75일에 버추얼 셋 하나 정도는 돌았던 것 같습니다. 방학 동안 버추얼 함께 돌아주셨던 cywohoy, kenn3n, hakuaa_2, 0917ba, meow_love, tjrn3712, kcits970, kolorvxl, lumitt, justin8021, jkrt2, aerae, Arpia님께 감사드립니다. 누구 빼먹지는 않았겠지? 저랑 같이 버추얼 돌았는데 빠져있어서 화나신다면 dm을 보내주세요.

그 덕분에 올해 codeforces에서만 400문제를 채웠습니다.

방학 내내 셋을 돈 덕분에 버추얼 기준으로는 퍼플을 찍었습니다. 이후 ICPC 인터넷 예선이랑 lgcpc를 시원하게 말아먹으면서 HCPC라도 잘 쳐서 상금을 쌀먹하려고 중간고사가 끝나자마자 버추얼을 신나게 돌렸습니다. 운 좋게 스피드 포스 셋을 빠르게 풀거나, div2E 정도의 문제가 저에게 잘 맞게 나와 비록 virtual이지만 오렌지를 달성할 수 있었습니다. 이때 기준으로 실제 rating으로도 퍼플은 금방 갈 거라고 생각했는데… 저점이 한도 끝도 없이 낮아서 블루에서 진동하는 그래프가 만들어졌습니다.

멘탈이 완전 나가있던 와중 방학이 찾아왔고, 기어이 버추얼 오렌지를 다시 찍었습니다. 이제 퍼플에 도달하는 건 시간 문제라는 생각이 많이 들었습니다. 결국 기어이 잘 치는 날이 찾아와버립니다.

(12/11 23:35 ~ 12/12 01:35), Codeforces Round 1070 (Div. 2)

• A : 우선순위를 잘 정해서 없애면 자신보다 앞에 큰 수가 있다면 그 수는 무조건 없앨 수 있습니다. 이를 이용해서 체크해주면 간단히 풀 수 있습니다.
• B : 연속한 0 집합의 길이의 max값이 답입니다.
• C : 가장 큰 홀수 코인, 짝수 코인 개수 순으로 내림차순으로 두는 것이 최적이고, 위 동전들을 다 채웠다면 앞에 홀수 코인을 2개씩 추가해주면 됩니다.
• D : ai가 0일 수 없기 때문에 ai가 작은 정점부터 이 정점이 가능한 경로의 마지막 항일 때, 이전 항으로 가능한 값을 가진 map이나 unordered_map을 정점마다 관리해주면서 dp를 해주면 됩니다.
• E : 0으로 만드는 연산을 안 할 때는 각 값마다 자신의 왼쪽에서 자신보다 큰 값, 오른쪽에서 자신보다 큰 값 중 작은 값과 합쳐 없어지는게 이득입니다. 이를 거꾸로 생각하여 작은 값부터 각 값을 기준으로 이전 값들로 없애지 않은 값들 중 자신의 왼쪽에서 자신보다 큰 값, 오른쪽에서 자신보다 큰 값 사이에 있는 값들은 이 값으로 없애는게 가능하고, 가장 최적입니다. 이를 이용해서 각 값을 없애는데에 필요한 비용을 세그먼트 트리의 lazy propagation을 이용해서 구할 수 있고, 이 합이 답이 됩니다. 0으로 바꾸는 연산도 해당 범위의 모든 값을 0으로 바꾸어 주는 것으로 처리할 수 있습니다. 따라서 이를 이용하면 문제를 해결할 수 있습니다.

(12/19 23:35 ~ 12/20 02:05) Codeforces Global Round 31 (Div. 1 + Div. 2)

• A : 아무리봐도 성질이 안 보이는데 브루트 포스를 짜는데 오래 걸릴 것 같지 않아 나이브를 짰습니다.
• B : 그리디하게 합친 현재 문자열이 앞에 붙는게 이득인지 아닌지를 판별해주면 됩니다. 바보 같이 이상한 걸 짜서 2번 틀리고 패널티를 잔득 먹고 AC를 받았습니다.
• C : k가 홀수일 때는 n을 k번 출력하는 것이 자명한 답입니다. 짝수일 때가 중요한데, 짝수일 때는 큰 비트부터 보되, 하나 이상의 값에서 해당 비트를 비워야 합니다. 첫 비트에서는 하나의 값을 비우는 것밖에 할 수 없고, 이후 그 값 자리에는 나머지 비트를 전부 포함하더라도 n을 넘지 않으므로 해당 자리는 자유롭게 비트를 채울 수 있는 자리가 됩니다. 이 관찰을 이용하면 맞을 수 있습니다.
• D : 그리디하게 현재 원의 가능한 r의 최솟값, 최댓값을 관리하면서 답을 구해나가면 맞을 수 있습니다.
• 전체적으로 무려 7번이나 틀려 패널티를 크게 받았지만, 패널티를 다들 많이 받는 셋이었는데다가, CD를 동시에 푼 사람이 몇 없어 퍼포먼스가 생각보다 잘 나왔습니다. 이 셋을 통해서 퍼플을 찍었습니다.

(12/27 23:35 ~ 12/28 02:35) Good Bye 2025

• A : Y가 2개 이상 있으면 불가능하고, 아니면 가능합니다.
• B : U를 기준으로 왼쪽, 오른쪽에 S가 무조건 존재하여야 하고, 가장 가까운 왼쪽의 S와 가장 가까운 오른쪽의 S와의 거리가 같아야 합니다. 이러기 위해서는 U가 두 개 이상 연속하면 안 됩니다. 두 개 이상 연속하는 U를 적절히 S로 바꿔주면 맞출 수 있습니다.
• C : 각 인덱스 i를 기준으로 초기에 i번째에 위치하는 값이 마지막에 남는 값일 때 최적이 무엇일지 계산합시다. i 뒤의 모든 값들은 무조건 부호를 바꾸는 것만 고를 수 있고, 이전의 값들은 1을 제외하고는 절댓값 값으로 고를 수 있습니다. 1은 무조건 기존 부호대로 적용하여야 합니다.
• D : m = 0, m > n/2, 0 < m <= n/2인 세 가지 경우를 잘 나눠서 각 경우에 해를 구성하면 풀 수 있습니다.
• E : 17번 이분 탐색을 하되, 매번 prefix와 suffix의 값이 같도록 쪼개는 방법을 이분탐색을 해서 구합니다. 여기서 쪼개는 방법이 존재하지 않으면 현재 array의 길이와 쪼개진 횟수에 답이 비례하고, 아니면 쪼개진 두 array 중 작은 array에 최댓값이 존재하므로 해당 array에서 이분탐색을 해주면 됩니다. 17 * 17 + 1 = 289 + 1 = 290으로 쿼리 수 제한에 들어옵니다.
• F : 전체 트리를 모든 흰 정점을 기준으로 해당 정점을 루트로 하는 서브트리이되, 해당 서브트리에서 흰색 정점이 존재한다면 해당 정점을 루트로 하는 서브트리를 뺀 트리 여러 개로 나눕시다. 루트는 실제 색과 상관없이 흰색 정점으로 취급합시다. 그렇다면 흰색 정점의 개수만큼의 트리 개수로 나뉘게 됩니다. 조합론적으로 접근하면 이 서브트리들을 순서대로 나열하여 결합하는 경우의 수가 답임을 알 수 있습니다. 이를 적절히 잘 구해주면 됩니다.

( 12/29 11:35 ~ 12/30 01:35 ) Educational Codeforces Round 186 (Rated for Div. 2)

• A : 2025가 존재하거나, 2026이 존재하지 않으면 0, 아니면 2026에서 6을 5로 바꾸면 되므로 1입니다.
• B : 어짜피 초콜릿을 번갈아 가면서 사용하여야 하므로 각 초콜릿을 먼저 사용하는 경우 답 중 최댓값입니다.
• C : 각 j에 대해 조건을 만족시키는 k의 개수 * n을 저장합시다. i에 대해 for문을 돌면서 가능한 j에 대해 해당 개수를 더해주면 됩니다.
• D : sum(ai) / n과 같은 값들은 같은 값들끼리, sum(ai) / n + 1과 같은 값들은 같은 값들끼리 서로 순서를 바꿔도 됩니다. sum(ai) / n + 1이 될 수 있는 값 개수를 세서 위를 수식을 잘 짜서 계산하자. 이때, 답이 0인 경우에 대해 예외처리를 잘 해주어야 합니다.
• E : 그리디하게 각 상자에 대해 이 상자에 선물을 담으면 만족하는 친구 중, zi – yi가 가장 큰 친구를 만족시키기 힘드므로 그 친구에게 줄 선물을 상자에 담읍시다. 상자를 전부 사용했다면 남은 친구들 중 zi – yi가 작은 순서대로 친구의 선물에 동전을 쓰면 됩니다.
• F1 : 힘이 더 낮은 순록을 아무리 많이 가지고 와도 힘이 높은 순록보다 썰매를 더 세게 당길 수 없고, 순록 61마리째부터는 있으나마나라는 관찰을 할 수 있습니다. 따라서 이를 기반으로 마지노선 순록 수를 구할 수 있습니다. 각 ci에 대해 최소한 썰매를 당기기 위한 충분한 힘을 가지기 위해 필요한 ci힘의 순록 수를 bi로 정의합시다. 어떤 순록 그룹에 대해 높은 힘을 가진 순록 수부터 비교했을 때 순록 수가 bi보다 많으면 무조건 가능한 조합이고, 적으면 무조건 불가능한 조합이며, 같으면 더 작은 힘을 가진 순록도 비교해야 합니다. 이를 수학 식을 잘 써서 경우의 수를 구할 수 있고, O(60nm)에 문제를 해결할 수 있습니다.

이렇게 연말에 갑자기 행운이 찾아와서 오렌지를 점수를 딱 맞추어 달성하게 되었습니다. 올해 마지막 라운드인데다가 여태까지 한 번도 잘 친적이 없는 에듀이고, 저번 퍼플 승급전 때 2문제가 핵 당해서 가지 못했던 것 극복한 것 같아 상당히 의미 깊습니다.

아직은 제가 ps, cp를 놓지 않아도 되는 것 같아 안심입니다… 새해가 밝았습니다. 이렇게 성취할 수 있게 여태껏 도와주신 분들께 감사드립니다. 이 글을 읽어주신 여러분들도 새해 복 많이 받으셨으면 좋겠습니다. 긴 글 읽어주셔서 감사합니다.