1/17 CP (KCPC 2025 + Codeforces 1073) 후기

뭔가 글 두 개로 쓰긴 애매할 거 같아서 하나로 묶었습니다.

 

온사이트 신청을 안 해서 온라인으로 나가게 되었습니다. Div. 1은 하다가 힘없이 털릴 거 같아서 Div. 2로 갈아타서 봤습니다. (원래 Div. 2는 내부인 대상으로만 한다고 하네요...)

밥 먹고 나자 대회가 시작해있어서 허겁지겁 컴퓨터를 키긴 했는데 A를 보니까 구현이 막막하게 생겨서 그냥 끌리는 문제 하나로 넘어갔습니다. 이 당시 저는 난이도 오름차순 정렬이라는 사실을 모르고 있었습니다.

 

0:22 - H [First Solve, +1]

대강 생각해보니까 K의 위치는 정해져있으므로 이들부터 옮긴 뒤 모든 P를 (끝쪽이 아닌) 한 뭉치로 옮기기 위해서는 최대한 중앙값 근처로 접근해야 한다는 아이디어가 빨리 잡혔습니다. 그런데 처음에 중앙값을 계산해놓고 최대/최솟값 조절을 처음 값인 거 마냥 조정해서 1WA 뜨고 맞았습니다. 그래도 나머지 분들이 대부분 ABC 푸느라 퍼솔 챙길 수 있었습니다. CP 하면서 인생 처음 퍼솔이여서 기분은 좋았어요 (사실 SUAPC에서 additionalpass05님이 한 적 있긴 한데 그 문제에 제가 관여한 게 하나도 없어서...)

 

0:29 - F [First Solve, +]

사실 이제 슼보를 보니까 대충 난이도 오름차순 순이다라는 파악을 했...는데 어차피 H가 풀려서 이 참에 퍼솔 최대한 많이 먹는다는 마인드로 F에 들어갔습니다. (사실 그 전에 I를 풀려고 했는데 막혀서 그냥 F로 넘어갔습니다.)

지문이 무서워보였지만 단순 포함 배제를 잘 사용하면 python pow로 쉽게 해결되는 문제였습니다.

 

0:44 - G [First Solve, +1]

대충 생각해보니까 누적합으로 하면 뚫릴까 싶었습니다. 가능한 케이스가 6가지가 끝이기에 모든 회전에 대해서 하드코딩을 했습니다. 다행히 6가지라는 경우의 수가 워낙 적어서 무지성 index로도 시간 내에 돌려졌습니다.

다만 맞기 전에 하드코딩 한 줄을 잘못 해서 한 번 틀렸습니다. 예제 처음 거만 체크해서 그런 듯... 아무튼 어찌저찌 퍼솔 해트트릭 달성 야호! 여담으로 Div 1의 변형 문제는 State가 48개더라고요... 저건 어케 푸는지 모르겠

 

0:54 - E [+1]

이 때 쯤이면 퍼솔이 다 사라져서 그냥 풀고 싶은 순서대로 푼 거 같습니다. 평범한 DP 문제입니다. 그런데 -1을 output하고 continue해야 하는데 그걸 안 넣어서 1WA 했습니다. 그냥 체크를 안 하고 내는 게 습관이 된 듯.... o(N^2)이 Div 1에 있다는데 그거도 업솔빙 해봐야 되겠습니다.

 

1:00 - D [+]

해 구성 문제입니다. N >= 999998 정도까지만 따로 경우를 만들면 나머지는 형태 하나로 처리가 가능합니다. 이거도 Div 1버젼이 흥미로워 보입니다.

 

1:06 - A [+]

A 치고는 구현이 빡센 건 맞는 거 같은데 그래도 결국 갯수 세기 + 많조분 문제라 브론즈는 맞는 것 같습니다.

 

1:07 - B [+]

1분 컷 했습니다. 대충 이차함수 최댓값이다라는 수학 직관 쓰면 됩니다.

13분 동안 4솔 하면서 CP 인생 처음으로 전체 1위를 10분 정도 달성했습니다. 아무래도 Div 1으로 대부분의 미친 고수분들이 빠지니까 그래도 경쟁력이 생긴 거 같습니다

 

1:33 - C [+3]

진짜 정신나가는 줄 알았습니다. 아이디어는 거의 바로 잡았는데 많조분 과정에서 health가 안 떨어질 때 멈추는 과정, 수식 정리 과정 (나눗셈이 두 번이라 floating point 이슈 있을 줄 알고 식정리를 좀 했습니다)에서 실수를 3번 정도 한 데다가 데이터세트가 그렇게 많은 거도 아니라서 자잘한 픽스를 한 뒤에야 맞았습니다. 그래도 다시 1위로 올라갔습니다.

 

2:31 - I [+]

여기부터 확실히 고전했던 것 같습니다. 전에도 언급했듯이 먼저 풀려고 했다가 안 잡혀서 나중으로 미뤘습니다. 근데 이제 풀게 I, J밖에 없었습니다. 그래서 생각난 게 레이지세그였습니다. 그런데 추가시간 없는 1초인데 N<=1e6이라 파이썬에서 할 생각을 바로 접고 C++에서 짰습니다. 이전에 쓰던 레이지세그 구현이 정말 엉망이라 최근에 푼 Reactor 코드를 개인 노트에 넣고 구현하니까 확실히 더 편하긴 했는데 그래도 그렇게 쉽진 않았습니다. 아무튼 660ms에 돌아서 약간 아슬아슬하게 골인했습니다. 나중에 badtreap님이 말하시길 Linear Solution이 존재한다고 해서 그거도 나중에 살펴봐야 할 듯...

 

3:39 - J [+]

마지막 문제는 처음에 N, M 범위 때문에 DP 같은 아이디어 잡아보려고 했다가 실패하고 전에 I까지 풀었던 과정에서 약간 힘이 빠져서 30분 동안 쉬고 오더니 발상이 잡혔습니다. (사실 N, M 범위는 별로 큰 의미가 없었습니다.)

대충 두 개의 서로 다른 문자가 있으면 패턴이 고정이다라는 점을 통해서 많조분을 하면 되는데 그거조차 식정리가 워낙 빡세서 모든 케이스 정리를 적절히 하는데만 30분이 더 걸렸습니다. 다행히 예제는 잘 준비되어있어서 억울한 WA 받는 일은 없었습니다. 그렇게 올솔

 

최종 결과

그렇게 10/10 905 min. 5위로 대회 마감했습니다. 뭔가 퍼솔 노리다 보니까 떨어진 감은 없진 않지만 그래도 올솔했으면 됐다 생각합니다. 대회 자체는 약간 관찰보다 케이스워크 구현 제대로 하기 쪽이였던 것 같던게 아쉬웠지만 그래도 전체적으로는 무난했던 것 같습니다. 

그리고 이번에 1위 분이 sk091204님이시던데 이번 SUAPC에 YCPC 1위 paracompact님하고 같이 나온다니 벌써부터 1위 후보 나온 거 같네요 으악

 

그걸 다 보고 나서 코포를 쳤습니다. 그래도 오늘 대회 결과하고 최근 5번 중 3번이 오렌지 퍼포였다는 점을 감안하면 그래도 이번에 기대가 됐습니다. 다만 이번이 분리 Div 1을 처음 본다는 점이 약간 불안하긴 했습니다. 원래 스피드포스가 장점이였는데 첫 문제부터 2C 난이도면 그 장점 자체가 사라지지 않나... 게다가 심지어 3시간 라운드라 이번에도 마지막 1시간을 날릴 준비 하고 있었습니다 😢

 

0:05 - A [+]

솔직히 B1 B2 안 풀리면 튀려고 했는데 그냥 A가 거의 바로 아이디어가 나오니까 그냥 가보자 마인드로 B 안 보고 제출했습니다. 지문이 문제를 더 어려워보이게 했던 것 같습니다

0:32 - B1 [+1]

대충 그리디하게 하면 되겠지 하고 돌리니까 처음에 틀리게 나왔습니다. 벌써부터 왜 레지했지라는 생각이 들었는데 다행히 곧바로 반례를 찾아서 (처음에는 이웃한 닫는 괄호를 모두 닫아야 한다 생각했으나 하나만 제거해도 충분했음...) 맞았습니다.

1:25 - B2 [+1]

그냥 DP 문제였던 거 같은데 모든 케이스 관리하는 게 빡셌습니다. 예제도 안 나오는 거만 몇 번이여서 수정을 매번 했습니다. 그래도 원래 디버깅 할 때 LLM에 의존하던 지금의 나보단 낫아진 것 같습니다. 그런데 엣지케이스 체크도 안 하고 내는 제 습관은 여전했는지 67x67x101 array를 101x67x67로 착각해서 RE가 일어났습니다. 좀 허무하게 점수 날린 거 같네요; 참고로 N<=100이였는데 O(N^3) 안에 풀리던 거 같네요. 왤케 제한 낮게 줬지

2:01 - C [+]

솔직히 B2까지는 장점이였던 스피드포스조차 못 해서 정말 큰일났다 생각하고 있었습니다. C는 인터랙티브였는데 끄적이니까 C 중에서는 꽤 간단한 관찰이 나왔습니다. 지난 번에 퍼플 승급할 때도 E에서 그런 인터랙티브 나와서 잘 본 건데 그냥 운이 잘 따라주는 건가 싶습니다. 머지소팅 쿼리 정리하는 형식이라 꽤 재밌게 풀었습니다.

그 뒤로는 D에서 아이디어가 안 잡혀서 59분 동안 아무거도 못 했습니다. 그냥 1시간 쉬는 게 정배가 맞는 거 같습니다.

그래도 C는 풀어서 퍼포 괜찮게 나오겠지 하고 보니까

ㅇㄴ +55 가야 마스터인데 +50가 떴습니다 캐럿에

그래도 5n 정도 올라가면 LLM 쓱싹한 뒤에 오렌지는 가겠지 하고 존버를 탔는데

점수 업뎃이 하도 안 되느라 그냥 잤습니다.

그래서 일어나고 보니

이거진짜에요?

?????

아니 이걸 +56을 주네

아무튼 진짜 어쩌다 2101 Master에 도달했습니다.

상당히 운이 따라준 거 같긴 했지만, 1달 전만 해도 '가능하긴 함?' 하던데다가 Expert -> CM에만 15라운드 정도를 치뤘던 걸 감안하면 이번에 한 5라운드 승급은 정말 행복합니다.

 

다음에는 솔직히 뭘 해야 할지 조금 더 생각해봐야 되겠습니다.

출제조건 C를 위해서 2200 찍기던가, 아니면 코포 내 문제 출제 요청이든가, 아니면 그냥 대체로 플레 랜다 해보기라든가 생각나는 게 많네요

이제 저점도 충분히 올린 거 같으니 이 참에 고점 올려보는 거도 좋을 것 같습니다... 오렌지 올라갔는데 지금까지 레드 퍼포가 없어요 ㅠㅠㅠ