Post

2025 KAIST RUN Spring Contest

2025 KAIST RUN Spring Contest

2025년 5월 5일 어린이날에 대전에 가서 카이스트 런 봄대회에 참가했습니다. 643점을 받아 참가자 49명 중 8위를 했습니다.

대회 이전

연휴 기간이라 오가는 기차표를 잡기가 어려웠습니다. 결국 왕복 KTX표를 구해서 어떻게든 다녀오긴 했습니다.

오전 10시에 대전역에 도착해 카이로 이동했습니다. 회장이 열리기 전 런 동방 부근에서 여러 명의 PS러를 만났습니다. 카이스트 명?물 퀴즈노스에서 점심을 대충 먹고 회장으로 이동했습니다.

12시쯤에도 N1의 문은 굳게 잠겨 있었습니다. 포스터에 적힌 flappybird님 전화번호로 “저 안녕원인데, 여기 어케 들어감?”을 시전해서 들어갔습니다. 아직 회장이 세팅 중이었고, 풍선 스탠드를 준비하는 걸 잠깐 도와줬습니다. 반/송년대회에 썼던 것과 같은 스탠드를 썼는데, Equinox_가 스탠드 조립하는 법을 모르길래 정해를 알려줬습니다. (나중에 제 책상에 꼽힌 풍선들은 정해와 다르긴 했습니다.) 여러분도 고등학교를 다니면서 대회장 세팅하는 것을 선행학습하시기 바랍니다.

스탠드를 준비하고 있으니까 참가자 몇 분께서 제게 자리를 물어보시더라고요. 다음부터는 운영으로 참가해야겠습니다.

저는 투 투 투 투 투 투 투 투 투 포후르라는 팀명으로 참가했고, 그래서 팀노트 1페이지에 퉁퉁퉁퉁퉁퉁퉁퉁퉁사후르 사진을 넣어갔습니다. 몇몇 분들이 좋아해 주셨습니다. 개인적으로는 APIO 2024 C 마술쇼 지문을 포함한 jk410님 팀노트가 제일 기억에 남습니다.

A번 (0:31 PAC(70), 0:32 AC, 32분)

  • 문제가 난이도순이었기에 A번부터 읽었습니다. 딱 봐도 경우의 수 DP 문제였습니다.
  • 세 번 정도 지문을 잘못 읽었습니다. 정확히 무슨무슨 실수를 했는지는 잘 모르겠습니다만 아무튼 처음부터 멘탈이 나갔습니다.
  • 그러나 결론적으로는 문제를 풀었습니다. 섭테 대회라 패널티가 쌓이거나 하진 않았습니다.

    Sol (Full Task)

  • 연속한 돌 묶음 하나는 단색이거나, 중간에 색이 한 번 바뀝니다. 따라서 길이 $T$의 연속한 돌 묶음으로 가능한 돌의 배치는 $2T$개입니다.
  • DP 배열 a[i]를 $i-1$번째 칸에 돌이 있고 $i$번째 칸에는 돌이 없는 $0\sim i$번 칸의 돌의 배치의 경우의 수라고 합시다. 그렇다면 s[i]는 $i$번째 칸에 돌이 없도록 채우는 모든 경우의 수입니다.
  • a에 대한 점화식을 다음과 같이 생각할 수 있습니다:
    • $i-1$번째 칸까지 채워진 연속한 돌의 수가 1인 경우: 채우는 경우의 수는 2이며, 그 앞에는 빈칸이 한 개 이상 있으면 됩니다. 즉 그 앞까지 채울 때 경우의 수는 2s[i-2]입니다.
    • 2인 경우: 두 칸을 채우는 경우의 수는 4이며, 그 앞까지 모두 채우는 경우의 수는 4s[i-3]입니다.
    • 6s[i-4], 8s[i-5]…를 다 더해주면 됩니다.
  • 즉 점화식은 s의 누적 합 배열 ssss의 누적 합 배열 sss에 대해 a[i]=sss[i-2]*2가 됩니다. 이를 계산해주면 됩니다.

B번 (0:38 AC, 6분)

  • A번에서 약간 멘탈이 나간 상태였지만, ioi식 스코어링을 사용했기에 따라잡으면 된다는 생각으로 B를 봤습니다.
  • 그리디 문제임이 확실해 보였고, 다행히 이번에는 구현을 틀릴 껀덕지도 없었습니다. 빠르게 풀고 지나갔습니다.

Sol (Full Task)

  • 배열의 값의 차의 합을 최대화해야 하므로, 값들이 최대한 멀리 떨어져 있어야 합니다. 예를 들어, 입력의 모든 값이 0이라면, 절반을 $1$으로 절반을 $M$으로 채우는 것이 자명하게도 최적입니다.
    • 다른 값을 전부 고정하고 하나의 값만 바꾼다 했을 때, 1이나 M에 두는 것이 최적임을 어렵지 않게 생각할 수 있습니다.
  • 그러므로 0 중 몇 개를 1으로, 몇 개를 M으로 바꾸면 그중 하나가 최대입니다. $O(M)$을 돌려도 되므로, 모든 케이스를 탐색하면 됩니다.
    • 이미 정해져 있는 값들의 합을 구해 두면, 1과 M의 개수가 정해질 때 값의 차의 합은 $O(1)$에 구할 수 있습니다.

C번 (0:50 WA, 0:57 AC, 19분)

  • B번을 빨리 밀고 왔기에 + 슥보에서 C가 많이 풀렸기에 C번도 빨리 밀고 지나갈 수 있지 않을까 싶었습니다.
  • 이것도 약간의 constructive를 섞은 그리디 문제였습니다.
  • 정확히 무슨 생각을 했는지는 모르겠지만 아무튼 path graph를 만들 수 있는지 확인하는 로직을 잘못 짜서 한 번 틀렸습니다. 근데 그냥 수의 개수 세서 2,2,…,2,0or1임을 확인하기만 하면 되길래 처음부터 다시 짰습니다. 다행히 구현에는 7분 정도밖에 쓰지 않았습니다.

Sol (Full Task)

  • 위에서 잠깐 언급했듯이, path graph를 만드는 것이 안정성이 높은 정점이 가장 많게 되는 방향입니다.
  • 어떤 트리에 대해서도, 정점을 하나씩 움직여서 path로 만드는 과정에서 모든 정점의 안정성이 유지 혹은 높아지도록 할 수 있음이 어렵지 않게 보입니다. 따라서 그리디가 성립합니다.
  • 안정성이 0 이상인 것이 2개, 1 이상인 것이 2개, 2 이상인 것이 2개…인지 확인하면 됩니다.

D번 (1:07 WA, 1:11 WA, 1:15 PAC(4), 1:31 WA, 1:35 WA, 1:37 AC, 40분)

  • constructive 문제를 또 만났습니다. 근데 어디서 시작할지 모르겠어서 처음에는 굉장히 막막하게 다가왔습니다.
  • $N \leq 4$인 섭테가 있었고, 이걸 풀기 위해 3과 4에서의 해를 먼저 찾아보고자 했습니다.
  • 어떻게 해도 3은 만들어지지 않았습니다. 2 빼고 모든 경우에서 0을 출력해봤는데 틀렸습니다.
  • 그래서 4인 경우를 열심히 구성해봤습니다. 그러다 어떻게 해서 하나를 건졌습니다.

Sol (Subtask 1)

  • 1, 3인 경우는 존재하지 않습니다. 2인 경우는 지문에 있는 대로 하면 됩니다.
  • 4인 경우 1 3 4 2\n3 1 2 4\n4 2 1 3\n2 4 3 1을 사용할 수 있습니다.

  • 건지고 나니까, $N$에서 해가 있으면 $2N$ 해를 만들 수 있을 것 같았습니다.
  • $N=4$가 $N=2$에서 구성되는 것을 그대로 가져다가 $N=8$을 그려봤고, 해가 나왔습니다.
  • $2^x$꼴에서는 해가 존재한다는 것을 알 수 있었습니다. 어차피 패널티가 없기에 이것만을 해결하는 솔루션을 짰고, 맞았습니다.

Sol (Full Task)

  • $2^x$의 해를 가져와서, 모든 원소에 ×2-1한 것을 A, ×2한 것을 B라 합시다.
  • B를 뒤집습니다.
  • AB\nBA가 $2^{x+1}$의 해입니다.
  • 2의 거듭제곱 꼴이 아닐 때 어떻게 되는지는 증명해보지 않았습니다.

E번 (2:17 PAC(48), 2:19 AC, 42분)

  • DAG 조합론 문제가 나왔습니다. 무언가 DAG와 그래프의 성질들을 잘 사용해야 될 것 같이 생겼는데, DAG에 대한 경험이 있는 편은 아니기에 약간 무서웠습니다.
  • 그런데 조금 생각해보니까, arborescence라는 조건 때문에 더블카운팅하면 그래프의 구조 같은 건 다 무시해도 될 것 같았습니다. 그래서 그렇게 긴 시간을 쓰지 않고 풀었던 것 같습니다.

Sol (Subtask 3)

  • 루트에서 어떤 정점으로 가는 경로가 정확히 하나 존재해야 합니다. 즉, 모든 정점에 대해 그 정점을 향하는 간선 중 정확히 하나씩만 골라주면 됩니다.
    • 이게 성립하지 않으려면 parent만 따라가다 보면 사이클 같은 게 생겨서 루트랑 이어지지 않아야 하는데, 처음 그래프가 DAG라서 그럴 일이 없습니다.
  • 따라서, 모든 정점에 대해 그 정점으로 가는 간선이 가지게 될 가중치의 기댓값을 계산하는 문제를 풀면 됩니다.
  • 이 값은 그 정점으로 가는 간선의 개수에만 영향을 받습니다. 개수 $x$에 대해, 값을 나이브하게 계산하면 $O(x\log x)$ 정도에 구할 수 있습니다. 그러면 제곱 정도에는 문제가 해결됩니다.

Sol (Full Task)

  • 3번 서브태스트에서 서로 다른 $x$값이 그렇게 많이 등장하지 않습니다. 따라서 이전에 나온 $x$값에 대한 함숫값을 메모이제이션해주기만 해도 제곱이 없어집니다.

F번 (2:57 WA, 3:02 WA, 3:09 WA, 3:13 WA, 3:14 WA, 3:16 WA, 3:17 WA, 3:19 AC)

  • 아, 기하입니다. 제게 대회에서 기하 문제는 보통 마지막으로 잡아서 결국 못 풀고 끝나는 문제기에, 혹시 이번에도 제 마지막 문제가 되려나 싶었습니다.
  • 뭔가 컨벡스 헐을 잘 써야 될 것 같아 보였습니다. 보통 기하 문제에는 일단 컨헐을 박으면 뭔가 보이기도 하고, 만약 모든 점이 컨헐 위에 있다면 무조건 불가능함이 보였기 때문입니다.
  • 컨헐을 그려놓고 이것저것 생각하다 보니 그리 어렵지 않게 답을 구성할 수 있음을 찾았습니다. 팀노트엔 당연히 graham scan이 있었고요. 그래서 다행히도 나름 빠르게 문제를 해결했습니다.

Sol (Full Task)

  • 모든 점이 볼록 껍질 위에 있다면, 그을 수 있는 선분의 수가 $2N-3$개밖에 안 되므로 -1을 출력하면 됩니다.
  • 주어진 점들을 각도정렬합시다. 각도정렬의 기준이 되는 점을 $X$라 하고 나머지 점들은 정렬된 순서대로 $P_1, P_2, \cdots, P_{N-1}$이라 합시다.
  • 이렇게 하면, $XP_1, XP_2, \cdots, XP_{N-1}$을 빨간색으로 칠하고 $P_1P_2, P_2P_3, \cdots, P_{N-2}P_{N-1}$을 파란색으로 칠하면 선분 하나 빼고 해가 완성됩니다.
  • 이때, 볼록 껍질 위에 있지 않은 점을 아무거나 하나 잡아서 $P_i$라 합시다. $i$는 $1$이나 $N-1$은 아님이 보장됩니다.
  • 볼록 껍질 위에 있는 점들 중 각도 정렬의 순서로 $P_i$ 바로 앞에 나오는 점과 바로 뒤에 나오는 점을 각각 $L$과 $R$이라고 합시다. 그러면 삼각형 $LRX$ 내부에 $P_i$가 있습니다.
  • $XP_i$와 $LP_i$와 $LR$을 파란색으로 칠하고 $P_iR$을 파란색으로 칠하면 두 트리가 완성됩니다.

G번 (3:21 WA, 3:34 WA, 3:36 PAC(10), 3:43 WA, 3:44 PAC(10), 3:46 PAC(10), 3:48 PAC(10), 3:50 PAC(20))

  • F까지를 풀고 나니까 한 자리 등수에 있었고, G랑 H는 많이 안 풀릴 것 같았습니다. 일단은 G를 보기로 했습니다.
  • 섭테를 긁는 것 말고는 딱히 좋은 전략이 생각나지 않았습니다. 그래서 일단 섭테를 긁고 넘어갔습니다.

Sol (Subtask 1)

  • 모든 칸에 1을 채워도 공격자가 이깁니다. AND가 0이고 합이 $2^N-1$인 아무 세 수를 출력하면 됩니다.

Sol (Subtask 2)

  • 조건을 만족하는 세 수가 1, 2, 4밖에 없습니다. 만약 $m$이 $n$ 이상이라면 대충 1, 2, 4를 021, 210, 102로 채우면 방어자가 이길 수 있습니다. 그렇지 않다면 1, 2, 4로 공격하면 공격자가 이길 수 있습니다.

H번 (4:43 WA, 4:43 WA, 4:46 RE, 4:47 PAC(12), 4:48 PAC(12), 4:48 WA, 4:49 PAC(23), 4:59 WA)

  • lighton이 G를 만점 받는 것을 보았지만 저는 더 이상 G에서 긁을 거리가 없어 보였고, 그래서 H로 넘어갔습니다.
  • 꽤나 자명한 제곱 정점 솔루션이 보였고, 구현했습니다.

Sol (Subtask 3)

  • 간단하게, $T$의 모든 정점을 정점 127개짜리 이진 트리로 만들면 모든 정점이 최대 128개의 거리가 같은 간선을 가지도록 할 수 있습니다. 그러면 어떤 그래프가 들어오던 construct할 수 있으므로 어떤 트리가 들어와도 구성이 가능합니다.

I번 (4:54 WA)

  • 안 읽었습니다.
  • 사실 읽긴 했습니다. 생각은 안 했습니다.
  • 1회 제출은 Text이며, 그 내용은 다음과 같습니다:
    • Such destiny was not kimgibumed,

대회 이후

  • flappybird가 문제가 어떻냐고 물어봤습니다.
    • A부터 F는 다 평타 이상은 하는 괜찮은 문제라 생각했습니다.
      • D번 증명 빼고요.
    • G랑 H는 일단 풀이를 알면 좋은 문제일 것 같다고 생각했습니다.
    • I(랑 G)는 ibm2006, Kaling, Kou, RIKKA, cocoa_chan 중 한 명이 냈을 것이라 확신했습니다.
    • 전체적으로 ibm2006, Kaling, Kou, RIKKA, cocoa_chan 중 한 명의 맛이 다소 강하게 느껴졌지만 그래도 좋은 셋이라고 생각했습니다.
  • G를 퍼솔한 lighton과 H를 퍼솔한 mjhmjh1104에게 각각의 풀이를 들었습니다. 둘 다 매우 잘 낸 문제라고 생각했습니다.
  • gs22123에게 ‘내가 프리즈 전에 비해 등수가 올라갔는지 떨어졌는지 알려달라’고 했는데, 둘 다 아니라 했습니다. 그래서 슥보 까기 전에 제 등수는 알고 있었습니다.

슥보까기

  • 프리즈 전을 기반으로 624나 632가 많을 것이라 생각했는데, 각각 한 명밖에 안 나왔습니다. 대신 620은 좀 많았습니다.
  • H의 subt 3은 자명하다고 생각했는데, H에서 23점을 긁은 사람이 주변에 없었습니다.
  • 추가로 긁는다면 I에서 10점을 더 긁었어야 하는데, 그래봤자 등수가 올라갔을 것 같지는 않습니다.
  • 전체적으로 섭테를 미는 건 잘 했습니다. G랑 H 중에 풀테가 생각났을 만한 문제는 없는 것 같습니다.
  • 6솔도 사실 플레를 다 밀어야 가능한 거라서, 플레를 다 밀었다는 사실에서부터 이미 만족하긴 합니다.
    • 근데 600점 컷이 20명인 건 좀 말이 안 되는 것 같습니다. 좃고수들…
  • 결과적으로 8등을 했습니다. 꽤나 등수가 잘 나와서 이 정도면 만족합니다.
  • 1등은 mjhmjh1104가, 2등과 3등은 각각 sorohue님과 jhwest님이 가져가셨습니다. 팬이에요!

뒷풀이

  • 에 갔습니다. 열심히 야부리를 털었습니다. 재밌었습니다.
  • 확실히 카이가 신촌보다 익숙합니다.
  • 테이블에서는 40..42기와 함께 mjhmjh1104님, kim16님, 노노님, 종이님, 니은님과 앉았습니다. 외에는 운영진을 비롯한 ^슈평^ 테이블, ^ibm^ 테이블, 그리고 포킹 분들을 비롯한 다양성 높은 테이블 하나가 있었던 것 같습니다.
  • 제 블로그를 읽는 분이 또 계셨습니다.
  • 기억나는 담화로는,
    • italian brainrot 팀명 얘기에서 시작해서 제 팀명의 유래에 대한 얘기가 잠깐 나왔습니다. 원래 범 범 범 범 범 범 범 범 범 쌀후르 팀명을 달고 오려 했으나, ibm2006이 지역·인종·성·종교의 차별·비하·혐오 등이 담긴 팀 이름에 해당한다고 해서 못 가지고 갔다고 했습니다.
      • 그리고 얼마 안 가서 서울대에 범 범 범 범 범 범 범 범 범 쌀후르가 등장했습니다.
    • 제 기차표가 이르다는 얘기를 하니까, 걍 런방에서 자고 가라는 얘기를 들었습니다. 사실 카이 친구 한 명의 방에 잘 수도 있는 상황이긴 했는데, 다음 날까지 대전에 있기는 싫어서 바로 왔습니다.

감사합니다.

This post is licensed under CC BY 4.0 by the author.