LGCPC 2025

2025년 9월 6일에 LG 대학생 프로그래밍 대회의 예선에, 20일에 본선에 참가했습니다. 팀명은 앨리스와_밥은_유명한_마술사이다로, 예선 성적은 212+271/400=#20으로 상위 60인 안에 들어 본선에 진출했으며, 본선 성적은 221+146/400=#18입니다.

예선

• A를 11분에, B를 34분에 풀었습니다. 200점을 받는 것은 쉬웠습니다.
• 대략 30분 정도를 C번에 박았습니다. 300점을 받는 것은 매우 어려워 보였습니다.
• 110분 정도에 C/D번에서 자명섭테만 긁었더니 등수가 한 자리였고, 무슨 짓을 해도 본선에 갈 것 같아서 접었습니다.

프리즈 이후에 등수가 많이 떨어졌지만, 그럼에도 20등으로 널널하게 본선에 진출했습니다.

본선

시작 이전

대회 당일이 연고전 2일차였습니다. 저는 금요일에 수업이 있는 관계로 금요일에 경기를 보지 않았는데, 그냥 토요일도 보이콧하고 LG에 놀러 가기로 했습니다.

팀노트가 필요한 대회였고, 전날에 평소 팀연습 때 쓰던 투 투 투 투 투 투 투 투 투 포후르 팀노트를 약간 수정해 가져갔습니다. ICPC 팀노트는 이 팀노트를 기반으로 작성하게 될 예정입니다.

포스텍 전준우가 서울역으로 올라온다길래 만나서 같이 점심을 먹고 회장에 들어갔습니다. 늘 그렇듯이 샵인클루드앳코더컨볼루션과 고죠사토루가 야부리를 털고 있길래 인사했습니다. 그러고 자리로 가니 앞자리가 UCPC 팀원인 sciencepark이었습니다. 외에도 RGB_ICPC를 달고 오신 몇 분과 인사했습니다.

자리 순서가 예선 등수 순이더라고요. 예선에서 제 바로 위 등수가 2시간 동안 ------허접------이었어서 누구신지 좀 궁금했지만, 아쉽게도 본대회에는 불참하셨습니다. 제 바로 아래 등수 분도 불참하셨고, 하필 제 자리가 대회장 앞에서 두 번째 줄 정가운데였기에, 꽤나 눈에 띄는 자리에 앉았던 것 같습니다. (사실 그건 별로 안 불편했고, 제 주변 자리가 쭉 비어있던 관계로 삼각대 카메라가 제 바로 옆에 설치되길래 부담스럽긴 했던 것 같습니다.)

0:00~0:03

• A번을 잡았습니다.
• 약간의 믿음을 가지고 구현했고, (사실 틀릴 리 없다고 확신하긴 했습니다,) 아무튼 맞았습니다.
• 3등이었습니다.

0:03~0:31

• B번을 잡았습니다.
• 바로 보이지는 않았습니다. 몇 가지의 아이디어를 떠올렸고, 15분 정도가 지나 서너 번째 아이디어로 낸 아이디어인 [길이][A개수] DP를 짜면 역추적만 할 수 있으면 된다는 것을 깨달았습니다.
• 구현했고, 생각보다 구현이 오래 걸렸고, 아무튼 두 번째 제출에서 AC를 받았습니다.
• 어쨌든 10등 언저리에 있었습니다.

0:31~0:40

• C번을 잡았습니다.
• 지문이 매직쇼로 가득차 있어서, 10분 정도 집중을 못 했습니다.

0:40~1:00

• 매직쇼의 유혹을 뿌리치고 C번을 이해하는 데 성공했습니다.
• $q\neq{0}$인 경우, 어차피 180턴 이후에는 이길 확률이 $0.5:0.5$ 혹은 $0:0$으로 수렴합니다. 따라서 $q=0$인 경우를 해결하면 $q\neq{0}$으로 가는 것은 그리 어렵지 않을 것 같다고 생각했습니다.
• $q=0$이면 뭔가 조합론적으로 문제를 풀 수 있을 것이라 생각했고, 식을 정리해 봤습니다.
• 섭테 2를 $O(N)$에, 3을 $O(N^2)$에 해결할 수 있음을 알아냈습니다.
• 섭테 3을 $O(N)$ 수준으로 줄일 수 있으면 풀테를 구현할 수 있을 것 같다고 생각해서, 여기에 시간을 박아봤습니다.

1:00~1:24

• 섭테 3을 잘 풀 수 있는 방법이 생각나지 않았습니다.
• 섭테 1과 2에 해당하는 코드를 구현해 제출해 20점을 받았습니다.

1:24~2:00

• D번 문제를 읽었습니다.
• 슥보를 보니 D번 문제를 긁는 것이 어려운 것 같아서, C번의 섭테 3에 시간을 더 박았습니다.
• 그러나 별 생각이 나지 않았습니다.

2:00~2:30

• 그러나 별 생각이 나지 않아서, D번으로 넘어갔습니다.
• 섭테 1이 긁기 쉬워 보였고 빠르게 해결해서 1점을 얻었습니다. (2:16)
• 그때까지도 D가 정말 안 긁혀서, C번에 시간을 조금 더 박기로 했습니다.
• 스코어보드가 프리즈되었고, 아마 10등 언저리에 있었습니다.

2:30~3:00

• C에서는 점수를 더 얻을 수 없을 것이라 결정하고 D를 긁는 데 시간을 박기로 했습니다.
• 섭테 4가 구현하기 어렵지 않아 보였고, 구현했으나 틀렸습니다를 받았습니다. (2:49)
• 틀린 부분을 알아냈고, 고쳤으나 시간 초과를 받았습니다. (2:56:00)
• TLE를 해소할 만한 부분을 수정했으나 시간 초과를 받았습니다. (2:56:42)
• 하나 더 찾았으나 틀렸습니다를 받았습니다. (2:58:03)
• 바보짓을 했다는 것을 알아내 수정했으나 시간 초과를 받았습니다. (2:58:19)
• 시간을 유의미하게 줄일 방법을 찾아 수정했으나 시간 초과를 받았습니다. (2:59:57)

이후

• 전준우가 초반에 많이 말렸던 것 같은데, 결과적으로 저와 동점이라는 것을 알았습니다.
• C3(과 C4)을 FFT로 해결할 수 있다는 것을 들었고, 듣고 나니 정말 자명하다고 생각했습니다.
• 특별상으로 야구잠바를 뿌리는데 야구를 안 보는지라 관심이 없었는데, 알고 보니 하나에 30만원씩 한다길래 관심이 있었어야 하나 싶은 후회가 약간 있습니다.
• 기업 대회라 기업 세션이 없어서 슥보를 빨리 까서 좋았습니다. 저는 18등으로 마감했습니다.
• 쌀품질맛협회에서 팀셋을 자주 돌았던 샌즈 고죠사토루가 3등상을, 연세대의 정상을 담당하고 계시는 쾨다구 RGB_ICPC3님이 2등상을 받아가셨습니다.
• 자리배치가 예선 등수 순인 것이 ‘상 받으러 나오기 편하게 하려고’라 하신 예선 1등 윤국조 조영욱님은 본선도 1등을 받아가셨는데, 2/3등이 모두 두 번째 줄 혹은 그 뒤에서 나왔으므로, 자기 발언에 대한 유일한 수혜자가 되셨습니다.
• 이후에 ibm 없는 ibm 저녁팟에서 밥을 먹고 집에 왔습니다.

후기

• KOI 2024-2와 비슷한 문제를 겪었습니다. 쉬운 문제를 빠르게 풀었으나, 어려운 문제의 쉬운 서브태스크에서 걸려서, 더 어려운 서브태스크로 넘어가지 못했습니다.
  • 단 이번에는 다른 문제의 서브태스크 사이에서 선택과 집중을 안 좋은 방향으로 해서 문제가 생겼네요.
• OI-like에서 풀테를 풀지 않을 생각으로 섭테를 많이 긁는 능력이 확실히 아직 많이 떨어집니다. (하나의 문제에 시간을 많이 박는 것에 더 익숙해서, 시간을 분배해서 잘 쓰는 능력이 부족하다는 뜻입니다.)
• 그건 그런데, 이제 정말로 올해 안에는 ICPC밖에 안 남았습니다. 따라서 당분간은 섭테 긁는 연습을 안 해도 되므로 ICPC에 올인합니다.