Day 244. 2023 대구소프트웨어고 프로그래밍 경진대회 (DPC 2023) Open Contest 후기

대회란 대회는 전부 참여했지만, 내가 이 대회 후기를 쓰는 이유는 1등 각을 봤기 때문이었다. 아무래도 인상이 깊었고... 그래서 후기까지 쓰게 되었다. 별개로 문제도 푸는 재미가 제법 있었고.

1등 각이 보였었다. D만 풀었더라면...

6문제짜리 대회에서 내 최종 성적은 5솔, 페널티 총합이 47분이었다. 로컬에서 디버깅을 열심히 하고 내는 습관 탓에 맞왜틀로 20분 추가 같은 불상사는 잘 일어나지 않고, 그래서 비슷한 실력 중에서는 스코어보드 가장 위에 있다.

1등이 6솔 페널티 총합이 107분이었고, 내가 F번까지 전부 푼 시점이 정확하게 25분이어서 35분 내에 D를 풀면 확실하게 1등을 탈환할 수 있었다. 그게 안 돼서 우승 후기 대신 참여 후기를 쓰고 있지만. 애초에 그래프 문제라서 내가 매우 약했다. D가 수학이고 E나 F가 골드 그래프였으면 5솔은 언감생심일 테니 5솔로 만족해야 하는 건 맞는데, 아쉬운 건 아쉬운 거다...

타임라인은 다음과 같다.

 

00:02 A AC

각 학생의 번호는 필요 없는 데이터이다. 모든 학생은 학년과 반에 따라서 과가 나뉜다. 과가 정의되지 않는 1학년부터 처리해 주고 나머지 학생들은 각 학생의 반에 따라서 나눠 주면 된다.

 

00:04 B AC

이 쪽이 가장 쉬웠다. 그냥 지문에서 주는 문자열에 따라서 처리해주면 되고 나머지는 molu를 출력하면 된다.

 

00:07 C AC

N번째 개미수열에서 이미 나온 수는 N+1번째 항부터 계속 개미수열에 등장하게 된다. X가 등장하면 다음 항부터는 무조건 X가 몇 개인지 세어 줘야 하기 때문이다.

어떤 수가 네 번 연속으로 나올 수는 없다. X가 X개, X가 X개 식으로 나열된 XXXX의 케이스는 X가 2X개로 축약할 수 있다. 또한 Y가 X개, X가 X개, X가 Z개 식으로 나열된 YXXXXZ 케이스는 Y가 X개, X가 (X+Z)개로 축약할 수 있기 때문이다. 그러므로 개미수열에 4는 등장하지 않는다.

따라서 개미수열을 이루는 수는 1, 2, 3뿐이고, 2는 제 3항부터 , 3은 제 6항부터 나오니 따라서 구현해 주면 끝이다. 증명이 조금 성가시긴 하지만 엄밀성 포기하고 Proof by AC로 퉁치면 더 금방 풀 수 있을 것이다. 나는 증명까지 마치고 구현해서 시간을 더 잡아먹었다. 그거 도외시했으면 1분은 더 단축할 수 있었을 것이다.

 

00:09 E AC

D가 그래프 문제이고 E랑 F가 제목에서부터 수학 냄새를 풀풀 풍기고 있길래 들어갔다. 누가 봐도 상용로그 쓰는 문제라 얼른 제출해서 AC를 챙겼다. 대회 마감 후 \(168^{6\,276\,559}\approx1.000\,000\,000\,061\,785\times 10^{13\,967\,285}\)같은 실수 연산의 허를 찌르는 케이스가 나와 지금은 슬프게도 채점 준비 중이 걸려 있다.

+) 파이썬 반례들이 쏟아져 나오고 있다. 내 코드를 빨리 바꾸지 않으면 재채점 과정에서 틀리게 될 것 같은데, 문제는 채점 준비 중이라서 제출을 할 수가 없다... Decimal 모듈을 잘 활용해야 재채점 후 AC를 챙겨갈 수 있을 듯 하다. 

 

00:25 F AC

종이에 식을 잘 정리하고, Python의 내장함수로 분할정복이 되기에 분할정복 구현하는 시간을 아낄 수 있었다. 예제에서 자꾸 552가 아니라 528이 나오기에 시간을 좀 잡아먹다가 식 깔끔하게 정리해서 구현 마쳤더니 그렇게 어렵지 않게 AC를 따낼 수 있었다.

 

~ 01:00 D

사실 여기까지는 스코어보드를 안 보고 있었는데, 전부 보고 D를 풀러 가기 전에 다른 사람들은 D를 어떻게 풀고 있으려나 하며 스코어보드를 열었더니 내 핸들이 제일 위에 있었다.

26분 시점 스코어보드

순간 뇌정지가 살짝 왔다. 버근가? 이거 100% 버그 같은데? 여기서 내가 D를 풀어버리면 확실하게 우승을 챙길 수 있었다. 바로 밑에 있는 riroan님과는 8분 차이가 있었기에, DFS 구현만 잘 하면... 문제는, 내가 대회 같은 촉박한 환경에서 DFS랑 BFS를 짜 본 적이 단 한 번도 없다는 것.

거기에 막상 우승이 눈 앞으로 다가오니까 오히려 머리가 더 안 돌아가기 시작했다. 큰 게임에 강한 사람들의 담력이 너무 부러웠다. 긴장이 퍼포먼스를 망치는 대표주자로서.

2위였던 riroan님이 D를 2번 틀리시더니 32분에 AC를 가져가셨다. 1위 패널티가 107분으로 결정된 순간이었다. 잘 푸는 사람에게 주어진 28분이라는 시간은 실버 풀기에 충분하겠지만, 나 같은 놈에게 주어진 28분은 인터넷에서 이것저것 찾다가 멸망하기에 딱 좋은 시간이었다.

 

01:00 ~ 본업 복귀

아무리 짜도 구현이 자꾸 망해서 예제조차 통과하지 못했다. 내가 뭘 잘못한 거지... 하는 생각을 할 시간은 없었다.

6시부터 9시까지 알바하던 학원에서 어제 시험 마친 원장님 아들 과외가 있었고... 늘어지는 원장님 아들 붙잡고 이 문제 이렇게 풀라고 알려주면서 짬짬이 코딩을 하는 것도 8시까지가 한계였다. 정확하게는 우승이 불가능하게 되자 우선순위가 후순위로 밀려난 것. 그냥 본업 복귀해서 이 자식 과외를 끝낸 다음 집에 가서 업솔빙 하자는 생각으로 노트북을 닫았다.

 

내 약점이 뭔지 확실히 알 수 있었던 꽤 좋은 경험이었다. 일단은... DFS랑 BFS 연습을 좀, 많이 해야겠다.