2025 KCPC Open Contest 후기

2026년에 개최된 2025 KCPC 오픈콘입니다. 백준 대회는 계속 1솔만 하고 도망가다가 이번에는 풀타임으로 풀어봤는데, 성과가 나쁘지 않아서 다행입니다.

조합 문제가 많아서 슬펐습니다. 코포치면서 강제로 조합론 공부를 더 하게 됐는데, 공부를 해도 여전히 싫어요.. 조합론 멈춰

예비소집#

PF번 — 01:53 AC#

문제에서 구해야 하는 180도 회전해도 같은 행렬을 151행렬이라고 하겠습니다.

나이브하게 하면 $O(N^2 M^2)$으로 안 되기 때문에 발상이 필요합니다.

어떤 행에서 가장 긴 151행렬을 찾는다면, 회전의 중심이 151행렬의 중심과 같은 부분 행렬들은 전부 151행렬입니다. 따라서 행을 고정하고 가장 긴 151행렬을 찾아주면 길이를 통해 개수도 알 수 있습니다.

구현은 중심행을 잡고 위아래로 확장하면서 추가된 행끼리 180도 돌려서 똑같은지 보고, 추가된 행에서 가장 긴 151행렬과 이전까지 찾았던 가장 긴 151행렬을 비교해서 $\min$을 가져갑니다. 매내처를 발라주는 게 핵심입니다.

0, 1, 2, 5, 8은 자기 자신에 대응되고, 6, 9는 서로에 대응되며, 3, 4, 7이 포함된 행렬은 절대 151행렬이 될 수 없으니 배제하면 됩니다.

$O(N^2 M)$ 정도로 문제를 해결할 수 있습니다.

본 대회#

A번 — 00:09 AC#

하란 대로 구현하면 되는 문제입니다. 보드를 굳이 배열로 만들 필요 없이 문자열 상태에서 푸는 게 더 편합니다.

C번 — 00:47 AC#

유일하게 제약이 걸린 쿼리는 P로, 큐의 크기가 0일 때 P를 쓰는 경우는 전체에서 제외해야 합니다.

$dp[i]$는 $i$번째 문자열까지 봤을 때 가능한 경우의 수라고 놓고 식을 세우면 $dp[i] = dp[i-1] + dp[i-2]$가 나옵니다.

하지만 매번마다 큐의 크기가 0일 때 P를 쓰는 경우를 계산할 필요는 없습니다. 그런 경우가 나오는 건 $(i-1) \% 3$이 0일 때뿐입니다. PP가 $+1$이고 P가 $-1$이니까 0이 되기 위해선 반드시 길이가 3의 배수여야 PP와 P가 매칭될 수 있어서 그렇습니다.

$(i-1) \% 3 = 0$이라면 큐의 크기가 0인 경우를 추가로 빼주면 되고, 직관으로.. 또는 규칙성을 보면서 그게 카탈란 수인 것도 알 수 있습니다. 저는 직관이 없어서 직접 항을 구했습니다. 카탈란인 거 눈치를 너무 늦게 챈 거 같아요. 식 정리도 좀 더 쉽게 할 수 있었을 거 같은데 아쉽습니다.

H번 — 01:03 AC#

제목 보고 거르려고 했는데 괜찮은 문제였습니다.

$n$이 2라면 2번 쿼리의 결과가 모두 1이거나 모두 0일 때만 가능하고, $n$이 3 이상이면 항상 가능합니다.

$n$이 3 이상이면, 시작부터 1번 쿼리로 구간 3개를 만듭니다. 이때 1번째와 2번째 구간은 겹치게, 3번째 구간은 안 겹치게 만듭니다.

나머지 1번 쿼리는 아무렇게나 씁니다. 그러면 이제, 2번 쿼리의 결과가 1이라면 2 1 2를 주고, 0이라면 2 1 3을 주는 간단한 방법으로 해결할 수 있게 됩니다.

$n$이 2라면 구간을 2개밖에 못 만들기 때문에 줄 수 있는 2번 쿼리는 2 1 2밖에 없고, 모두 1이면 두 구간을 겹치게, 모두 0이면 두 구간을 안 겹치게 만들면 됩니다. 그렇지 않다면 불가능합니다.

D번 — 01:13 WA#

뭔가 문제 그림이 기하 공포증을 유발해서 도망가려고 했는데, 생각보다 쉬운 케웍 문제라 바로 잡았습니다.

아무도 D를 안 풀었길래 퍼솔할 생각에 싱글벙글하다가 C가 K를 완전히 감싸는 경우를 생각하지 않아서 WA를 받았습니다.

D번 — 01:15 WA#

급하게 고쳤는데 K의 위와 아래를 막는 방법을 생각하지 않아서 WA를 또 받았습니다.

D번 — 01:17 AC#

$K + C + P$가 1이면 불가능합니다.

C와 P는 다른 문자가 1개라도 있으면, 무조건 규칙을 지키게 배치할 수 있습니다. 따라서 주요한 분기는 K에 달려 있습니다.

K가 0개일 때: 항상 가능합니다. CP를 짝을 이뤄서 붙이고, C가 남으면 CC...CP처럼 붙여주면 됩니다. P는 끝점이 1개라 더 쉽습니다.

K가 1개일 때: C가 K를 완전히 감쌀 수 있기 때문에, C가 1개 이상 있으면 항상 가능합니다. C가 0개라면, P가 적어도 2개는 있어야 가능하게 됩니다. K의 위와 아래를 P로 막아주면 됩니다.

K가 2개 이상일 때: K를 상하방향으로 쭉 배치해서 연결하면, 맨 윗부분과 맨 아랫부분만 막아주면 된다는 걸 알 수 있습니다. $C + P$가 2 이상이면 항상 가능합니다.

F번 — 01:48 WA#

4솔을 하고 슼보를 보니 F가 많이 풀려 있었습니다. 그래서 적당히 쉬운 문제인 줄 알았는데, 속았습니다. 조합 문제가 또 나와버렸습니다.

또 나만 모르는 웰노운으로 풀리는 그런 문제인가 하면서 지문을 읽고 보니까, 그냥 포함배제 쓰는 간단한 문제가 맞았습니다. 그래서 두 번 속았습니다.

근데 다 풀고 수의 범위 $v = r-l+1$이 1이면, $v-2$가 음수라서 $\max(0, v-2)$로 처리해야 하는데 안 해서 WA를 받았습니다.

식 정리한 거 그대로 쓰면 되는 건데 $\max(0, v-1)$은 잘 해놓고 왜 안 했지

F번 — 01:49 AC#

원소로 들어갈 수 있는 숫자는 $v$개가 있습니다. 가능한 전체 경우의 수는 $v^n$입니다.

여기서 $l$이 없는 경우가 $(v-1)^n$개, $r$이 없는 경우도 똑같이 $(v-1)^n$개이고 둘 다 없는 경우는 $(v-2)^n$개입니다.

따라서 경우의 수는 $v^n+(v-2)^n-2(v-1)^n$개이고, 기댓값을 물어보고 있지만 결국 정렬이 성공하는 경우는 1개밖에 없어서 경우의 수랑 똑같습니다.

J번 — 03:21 AC#

5솔을 하고 슼보를 보니 J가 많이 풀려 있었습니다. 그래서 적당히 쉬운 문제인 줄 알았는데, 속았습니다. 조합 문제가 또또 나와버렸습니다.

일단은 초반에 몇 줄만 결정하면 이후에 자동으로 나머지 칸들이 결정된다는 관찰을 하고 나서, 이걸 전체로 확장시키려고 하다가 실패했습니다. 막 $n$이랑 $m$의 홀짝에 따라서 어쩌구 하는 걸 다 썼었는데, 작은 예제는 돌고 큰 예제가 안 돌아서 망했단 걸 직감했습니다.

그래서 K와 P를 어떤 관계로 배치시키는지에 중점을 두고 문제를 풀었습니다. 관찰이 좀 오래 걸렸는데, 나눈 경우는 4가지 정도이고 방향으로 보면 행 방향, 열 방향, 대각선 방향 중 하나로 K, P가 돌아가면서 나오는 게 유지가 되기 때문에 이를 기반으로 식을 세울 수 있었습니다. 경우를 나누면 나눌수록 점점 헷갈려져서 KPKP KCKC PCPC KCPC PCKC 이런 배열들을 일단 다 써놓고 분류해서 정리했는데, 결과적으로는 잘한 선택인 것 같습니다. 관찰하고 케이스 정리하는 게 모두 어려운 문제였습니다.

B번 — 03:54 TLE#

남은 시간 동안 E번이나 I번은 못 푸는 게 확실했습니다. B번보다는 G번이 좀 더 재밌어보여서 먼저 G번을 관찰했는데, 점 하나가 원점에 고정되어 있어서 적절히 도착점을 원점 근처로 이동시켜도 될 거 같다는 생각만 들고 증명하진 못해서 B번으로 왔습니다.

1번 정점에 2, 3, 4번 정점을 연결합시다. 무거운 정점은 4개 이하여야 하므로, 2, 3, 4번 정점을 전부 무거운 정점으로 만들어도 조건은 만족합니다. 2번 정점에 $a$개의 정점을 연결하고, 마찬가지로 3번 정점에 $b$개, 4번 정점에 $c$개를 연결하면 트리의 지름 개수는 $ab+bc+ca$가 됩니다. 이제 $ab+bc+ca = N$을 만족하는 $a, b, c$를 찾으면 됩니다. 근데 문제는 어떻게 찾느냐입니다.

가장 먼저 떠오르는 방법은 브루트포스로 찾는 거였습니다. $N$ 제한이 $10^{11}$이었지만 $a$를 고정시켜놓고 찾으면 빠르게 돌릴 수 있어서 시간 내에 돌아간다고 생각했습니다.

당연히 아니었습니다! 예를 들어 $a = 1$일 때 나오는 식인 $bc+b+c=N$을 변형하면 $(b+1)(c+1)=N+1$이 되기 때문에 단순히 $N+1$이 소수면 $O(N)$이 되어서 시간초과를 받게 됩니다. 나중에 다른 분 풀이를 보니 탐색을 $\sqrt{N+1}$부터 하니까 AC를 받았다고 하는데, 왜 도는지 증명도 모르겠고 그냥 고능하지 못했던 거 같습니다.

이와는 별개로 시복 문제를 해결하기 위해 랜덤을 사용하는 풀이도 된다고 하는데, 저는 랜덤도 안 떠오르고 결정론적 방법도 말아먹어서 여기서 손을 놨습니다.