2025 고려대학교 프로그래밍 경시대회(KCPC) 후기 - 2

~ 대회장 입실

 어쩐지 잠을 네 시간 밖에 못잤습니다. 대충 준비하고 집을 나서서 무인프린트카페에 들러 팀노트를 출력했습니다. 팀노트는 예전에 ICPC 때 만들었던 걸 팀명만 바꿔서 사용했습니다. 사실 팀노트를 사용할 일은 딱히 없을 것 같기는 했습니다. 예비소집 문제들도 어려운 알고리즘을 요구하지 않았고, 솔브드 기준 플래티넘 이하 알고리즘들 중에 알고 있는 것들은 대부분 구현을 암기하고 있기 때문입니다. (그 이상은 어차피 팀노트 봐도 풀 자신이 없었고요...) 그래도 팀노트 챙겨서 손해볼 일은 없을테니 일단 출력했습니다. 대회장까지는 지하철로 갔는데, 노트북이 가벼운 편은 아닌지라 힘들었습니다. 하필이면 이 날따라 지하철에 사람이 매우 많아서 굉장히 피곤하게 이동했습니다. 고려대에 도착하고 보니 시간이 조금 있었는데 대회 직전이라서 뭘 많이 먹기는 좀 부담스럽고, 편의점에서 컵라면으로 점심을 때웠습니다.

 

 

대회 전

 대회장 앞에서 등록을 하니 몬스터 한 캔을 같이 나누어 주었습니다. 대회장 앞에 있는 생수 한 병과 젤리 몇 개를 챙겨서 자리에 앉았습니다. 노트북을 켜서 이것저것 확인하고 나니까 시간이 조금 남아서 그냥 쉬었습니다. 도중에 wapas님을 만나서 간단하게 인사하고 자리에 앉았습니다.

 

 

 

본대회

 가장 먼저 A번을 확인했습니다. 읽다보니 대충 bfs나 dp 같은 거 열심히 써서 게임 구현하는 문제처럼 보여서, 제일 쉬운 게 이 난이도면 오늘 문제도 엄청 불셋이구나 싶었습니다. 열심히 이런저런 생각을 하고 있었는데 정작 읽고보니 지문의 많은 부분이 풀이에 필요하지 않고, 그냥 맵의 난이도를 결정하는 법만 알면 되는 문제였습니다.

 

[00:06:30] A번 AC

 

왠지 문제 이름들을 보니 H가 풀고 싶어져서 H로 이동하였습니다. 간단하게 쿼리열을 구성하면 되는 문제인데, 문제를 잘못 읽어서 2번 쿼리에 a, b는 주어지는 건 줄 알았습니다. 복잡하고 예외가 많은 문제라고 착각하고 D로 이동했습니다. D는 보니까 C랑 P의 합이 둘 이상이면 무조건 가능하다는 것이 쉽게 보였습니다. 그게 아니면 당연히 안 되겠지 싶어서 바로 제출을 했지만 WA를 받았습니다.

[00:34:24] D번 WA

 

뭔가 예외가 있다는 건데, 갑자기 엄청 복잡한 문제로 보여서 일단 넘어갔습니다. 삽질을 하는 동안 H가 상당히 많이 풀린 것을 보고 문제에서 뭔가 잘못 읽었다는 것을 깨달았습니다. 다시 읽어보니 간단한 문제라는 걸 깨달을 수 있었고 풀이를 제출해서 AC를 받을 수 있었습니다.

 

[00:49:48] H번 AC

 

이후 F를 봤습니다. 당연하지만 어떤 배열을 정렬하여 얻을 수 있는 배열은 항상 정확하게 하나입니다. 따라서 최댓값이 R, 최솟값이 L인 길이 N 배열이 몇개인지 세면 기댓값을 구할 수 있습니다. 포함 배제 원리를 이용하면

(모든 정수 $1 \leq i \leq N$에 대해 $L \leq B_i \leq R$인 길이 N 배열의 수)

- (모든 정수 $1 \leq i \leq N$에 대해 $L \leq B_i \leq R-1$인 길이 N 배열의 수)

- (모든 정수 $1 \leq i \leq N$에 대해 $L+1 \leq B_i \leq R$인 길이 N 배열의 수)

+ (모든 정수 $1 \leq i \leq N$에 대해 $L+1 \leq B_i \leq R-1$인 길이 N 배열의 수)

로 구할 수 있다는 것을 알았습니다. 이는 $(R-L+1)^N - 2 \cdot (R-L)^N + (R-L-1)^N$를 계산하면 됩니다. 다만 $R = L$때는 (모든 정수 $1 \leq i \leq N$에 대해 $L+1 \leq B_i \leq R-1$인 길이 N 배열의 수)가 0이어야 하는데 예외처리를 안 해줘서 한 번 틀렸습니다.

 

[00:57:14] F번 WA
[00:58:30] F번 AC

 

스코어보드를 보니 이번엔 D가 많이 풀려있었습니다. 또 뭔가 잘못 생각했다는 걸 깨닫고 D로 돌아갔는데 아무리 생각해도 $C+P \geq 2$는 확실한 것 같고 예외는 보이지 않았습니다. K를 이상하게 붙여보다가 아닌 것 같아서 문제를 잘 읽어보니 $K \leq 3$이라는 조건이 눈에 들어왔습니다. 이 조건 하에서는 K가 이상하게 붙어서 답을 만드는 건 불가능 해보였고 $K = 0, 1, 2, 3$에 대해 하나씩 검증해보니 K 하나와 C 하나를 붙여서 조건을 만족시킬 수 있다는 것을 알게 되었습니다.

 

[01:11:41] D번 AC

 

이후 E를 읽어보았습니다. 뭔가 간단하게 바꾸는 방법이 있을까 생각해봤는데 XX를 X 두 개로 읽던 XX 하나로 읽던 결고에 영향이 없다는 것을 알았습니다. 따라서 각 문자가 바뀌는 구간에만 집중하면 될 듯 한데... 그 부분은 딱히 규칙이 안 보여서 자료구조를 사용하는 방법으로 생각을 틀었습니다. 세그먼트 트리에 집어 넣고 BOJ 24550번(이 멋진 수열에 쿼리를!)처럼 합성해주면 될 것 같다는 생각을 해봤습니다. 근데 일단 각 연산에 대한 연산표가 있어야 하는데 머리가 잘 안 돌아가서 일단 보류했습니다.

그 다음으로는 C를 잡았습니다. Catalan Triangle과 누적합으로 답을 구할 수 있다고 생각했는데, 안타깝게도 공식이 기억나지 않았습니다. 팀노트에도 없었고요... 그러면 유도를 해볼 수 있지 않을까 싶었는데 그 전에 시간 복잡도가 안 된다는 것을 깨닫고 보류했습니다. 관찰을 조금 해보니 Catalan Triangle의 점화식이 보였고, 구하고자 하는 값도 $c_{n, k}$꼴의 합이니 비슷한 점화식을 만족시킬 거라는 생각이 들었습니다. 관찰을 더해보니 $3N + 1$꼴일 때 카탈란 수 $C_{N \over 3}$이 하나씩 붙여주면 된다는 것을 알았습니다. 근데 경우의 수가 0인 경우에 0이 아니라 -1로 예외처리 해주라는 지문 내용을 못봐서 한 번 틀렸습니다.

 

[01:52:46] C번 WA
[01:54:23] C번 AC

 

B번과 J번이 풀려있는 것을 보고 우선 J를 잡아봤습니다. 정말 열심히 관찰을 하니 규칙이 보였습니다. C가 들어갈 칸을 일단 먼저 정한 다음에 남은 칸에 K와 P를 채우면 되는데 C가 들어가는 칸을 유효하게 정하려면 다음 두 조건 중에 하나를 만족해야 합니다.

1. 임의의 행이 인접한 행을 반전시킨 것과 동일한 모양이어야 한다.
2. 임의의 열이 인접한 열을 반전시킨 것과 동일한 모양이어야 한다.

그러면 행 하나를 임의로 구성하여 1번 규칙에 따라 전체 자리를 구성하는 방법, 열 하나를 임의로 구성하여 2번 규칙에 따라 전체 자리를 구성하는 방법 두 가지를 생각할 수 있습니다. 이 때 체크무늬처럼 구성하는 방법 2가지는 양쪽에 모두 포함되니 포함 배제 원리에 따라 2를 빼주면 됩니다. 그러면 C를 배치하는 방법은 $2^N + 2^M - 2$가지입니다. 이제 K와 P를 남은 공간에 채우는 방법의 수를 곱해주면 되는데 딱 한 칸만 정해주면 나머지는 자연스럽게 결정되는 것처럼 보였습니다. 그래서 답이 $2 \cdot (2^N + 2^M - 2)$라고 생각했지만 예제부터 틀린다는 것을 깨닫고 좀 더 고민해봤습니다. 문제에 있는 그림을 보며 점검을 해보니 C가 들어가는 칸을 줄무늬 모양으로 결정하면 각 줄 별로 독립적으로 K와 P를 채워줄 수 있다는 것을 알 수 있었습니다. 최종적으로 정답은 $2 \cdot (2^N + 2^M - 6) + 2^{\lfloor {N+1 \over 2} \rfloor} + 2^{\lfloor {N \over 2} \rfloor} + 2^{\lfloor {M+1 \over 2} \rfloor} + 2^{\lfloor {M \over 2} \rfloor}$입니다.

 

[02:45:32] J번 AC

 

I번은 너무 어려워보여서 B와 G를 고민해보려고 했습니다. 이때쯤 스코어보드상으로 외부 6등이었기 때문에 한 문제를 더 풀지 못하면 위험하다는 생각을 했습니다. B는 $ab+bc+ca = N$이 되도록 a, b, c를 잘 잡아주면 해결되는데, 문제는 그런 값을 어떻게 찾아야 하는지를 몰랐습니다. 아무리 생각해도 깔끔한 아이디어가 안 떠올라서 적당히 해가 나올 때까지 찾는 방법을 시도해봤습니다. 그런 a, b, c가 항상 있을 것이라는 것과 적당히 순서를 주면 찾는 게 그렇게 오래 걸리지는 않을 거라는 믿음으로 코드를 작성했는데 자꾸 잔실수가 났습니다. (a, b, c의 합을 제대로 체크를 안 한다던지...)

 

[03:55:03] B번 WA
[03:56:51] B번 WA
[03:59:16] B번 WA

 

그러던 중에 대회가 끝나서 결국 B는 풀지 못했습니다.

 

 

 

대회 후

 B는 정말 시간이 몇분만 더 있어도 풀었을텐데 너무 아쉬웠습니다. 프리즈 전에 외부 6등이고 그 사이에 아무것도 못했으니 상을 받을 가능성은 거의 없어보였습니다만 열어보기 전에는 모르는 거라고 생각하며 애써 무시했습니다. 아쉬운 마음에 문제지나 좀 더 보다가 짐 정리를 하였습니다. 조금 쉬고 있다보니 오늘도 역시 Kahoot 이벤트가 있었습니다. 빠르게 찍어서 고득점을 노려보았으나 처참한 찍기 실력 (3~4문제 맞은 걸로 기억합니다) 때문에 아무 의미가 없었습니다.

 

(대충 하지만 빨랐죠 짤)

 

 

 

스코어보드 공개

신기한(...) 닉네임들이 많네요

 이후 스코어보드 오픈이 있었습니다. 위로 한 명이라도 올라가면 순위상에서 쫓겨나는 상황이었지만 거의 기정 사실이었던지라 별로 긴장하며 보지는 않았던 것 같습니다. 예상했던 것처럼 순위가 밀려나서 전체 11등(외부 8등)으로 마무리하였습니다. 특별상도 전부 떨어져서 좀 슬프지만 고수 절취선 위에 있는 걸로 위안 삼아야겠습니다. 전반적으로 패턴 찾기와 조합론이 많았던 것 같은데, 패턴 찾기 쪽이 아무래도 좀 실력이 부족해서인지 실수도 많았고 시간 분배도 많이 말렸다는 생각이 드네요... 그래도 실력에 비해서 결과는 좋게 나온 편이라 이 정도면 만족해도 괜찮을 것 같습니다.