2024 HCPC 후기

제11회 한양대학교 프로그래밍 경시대회(HCPC) Advanced Division에 '신_섭이HCPC를정상화하네' 팀으로 참여했습니다. (jjaewon9, andrewmjk1, firstin0907)

 

보통 HCPC는 ICPC 팀원끼리 나가는 경우가 많은데, 저는 현재 휴학 상태라 HCPC를 같이 나갈 사람이 없었습니다. 그냥 아무나 데려가서 원맨팀이라도 해야하나 고민하던 찰나, 올해 ICPC에서 교내 1등을 한 BetterthanO1 (ingyu1009, andrewmjk1, firstin0907) 에서 ingyu1009이 검수로 런을 쳤다는 소식을 듣고 재빠르게 합류했습니다. 팀명은 팀원 세명 중 한명의 이름이 '신_섭'이라 그렇습니다 ㅋㅋ

 

팀연습같은건 안했고, 심지어 firstin0907님과는 대회 당일 처음 뵈었습니다. 그래도 개개인의 능력이 출중하니 충분히 1등할만 하다고 생각했습니다. 굉장히 오만하게도 대회 전에는 gggkik와 dohoon이 있는 팀을 제외하고는 경쟁자라고도 생각하지 않았구요...  과연 어떻게 됐을까요?

---

제가 ABCD, andrewmjk1이 EFG, firstin0908이 HIJ를 읽기로 하고, 대회에 돌입했습니다.

문제 목록

 

A를 읽었습니다. 뭔가 케웍을 개 열심히 하면 될거 같지만 하기 싫다는 생각을 하고 넘겼습니다.

 

B를 읽었습니다. 이 문제가 얼핏 떠올랐습니다. 트리 좋아하는 andrewmjk1에게 줘야겠다는 생각을 하고 넘겼습니다.

 

C를 읽었습니다. dp[5000][10][10][10]을 하면 되겠다고 생각했지만, 하기 싫다는 생각을 하고 넘겼습니다.

 

D를 읽었습니다. strict weak ordering이 생각났습니다. 내장 sort 함수에 주어진 행렬을 넣고 runtime 에러가 나는지 확인??(이게 가능한건진 모릅니다) 같은 생각이 빠르게 지나갔지만, 개에바인거같아서 넘겼습니다.

 

빠르게 4문제를 훑었지만, 당장 쉽게 짤 수 있는 문제는 안보여서 잠깐 얼을 탔습니다. 그러던 와중 옆에서 andrewmjk1이 F가 날먹이라며 빠르게 짜서 제출하길래 옆에서 구경을 했습니다.

F AC [+] (5min, First to Solve)

 

F 퍼솔인지 확인하려고 스코어보드를 보니, D가 풀려있었습니다. 다시 정신차리고 읽어보니 그냥 쉬운 문제여서 제가 열심히 짜고 맞췄습니다.

D AC [+] (17min)

 

제가 다시 A, B, C를 뒤적거리고 있던 사이, firstin0907와 andrewmjk1이 I와 G를 빠르게 밀었습니다.

I AC [+] (24min)

G AC [+] (26min)

 

그 사이 저는 그냥 C에서 dp[5000][10][10][10]을 그냥 하는게 맞다고 결심을 굳혔습니다. 어떻게 구현하는게 편할까 고민하던 중, 왠지 모르게 15000*9^6(~80억)이 시간 안에 돌고 구현도 무지성 7중 for문으로 될거같다는 아주 이상한 판단을 내렸습니다. 열심히 짜서 제출했더니 WA를 받았습니다.

C WA [-1] (38min)

 

다시 보니 초기화를 잘못했길래 고쳐서 제출했더니, 이번에는 TLE를 받았습니다.

C TLE [-2] (47min)

 

다시 코드를 읽어보고 택도없는 시간복잡도인걸 깨달았고, 코드를 밀고 다시 짰습니다. 상당히 고통스러웠고, 심지어 또 틀렸습니다.

C WA [-3] (58min)

 

더이상 머신을 잡고 있으면 안될거 같았습니다. A와 B의 풀이가 나온 andrewmjk1에게 머신을 넘기고 화면 구석에 C 코드를 띄워달라 한 뒤, 열심히 눈버깅을 했습니다. 아무리 봐도 모르겠길래 멘붕이 왔습니다. 환기를 위해 E를 보고있던 firstin0907에게 붙었습니다. 뭔가 풀이가 나왔다길래 설명을 들었고, 잘 이해는 못했지만 그럴듯한 것 같아서 알겠다고 했습니다. 그 사이 andrewmjk1가 열심히 A를 짜서 제출했지만, WA를 받았습니다.

A WA [-1] (69min)

 

다시 andrewmjk1에게 붙어서 같이 디버깅을 했지만, 코드는 굉장히 잘 짠 것 처럼 보였고 케웍에서 빼먹은게 있지 않은 이상 맞는 코드 같았습니다. andrewmjk1는 빼먹은 케이스가 있는지 검토하러 가고, 저는 C 코드를 다시 천천히 읽었습니다. 여전히 개 맞는 코드같아서 멘탈이 굉장히 흔들렸습니다.

 

andrewmjk1가 케이스 하나를 빼먹었다며 코드를 몇줄 추가하더니, 다행히도 AC를 받았습니다.

A AC [+1] (97min)

 

일단 C를 붙들고 있으면 안될 것 같았고, andrewmjk1가 B 풀이에 대해 설명을 들었습니다. 역시나 잘 이해는 못했지만 그럴듯한 것 같아서 알겠다고 했습니다. andrewmjk1가 그대로 머신을 잡고 B를 구현했지만, 출력 초과를 받았습니다.

B OLE [-1] (110min)

 

이해는 못했지만 설명해줬던 풀이를 다시 읊어주니 뭔가 놓친 부분이 있다고 하며 andrewmjk1가 B를 고쳐서 냈지만, WA를 받았습니다.

B WA [-2] (114min)

B WA [-3] (116min)

 

그동안 저는 C를 다시 짜기로 마음먹었습니다. dp[i]를 구하기 위해 true인 dp[i-1]의 상태를 참조하는 것이 아니라, dp[i]가 true인 상태들에 대해서 dp[i+1]을 true로 넘겨주는 식으로 구하면 훨씬 구현이 편해진다는 것을 캐치했고, andrewmjk1가 B에 박는 동안 손코딩으로 꼼꼼히 코드를 완성해둔 상태였습니다. 머신을 넘겨받아 빠르게 짜서 제출했고, 정말 다행히도 AC를 받았습니다. 아직도 이전 코드가 왜 틀리는지는 잘 모르겠습니다.,,

C AC [+4] (119min)

 

동시에 스코어보드가 프리즈되었습니다.

 

 

꽤 말렸습니다. B E를 반드시 풀고, 아직 노솔브인 H와 J 둘 중 하나는 풀어야 수상권에 들 수 있겠다는 생각이 들었습니다.

 

C를 AC받은 뒤에는 andrewmjk1가 머신을 잡고 B에 박고 있었고, 저는 firstin0907에게 다시 붙었습니다. 아까 설명했던 E 풀이는 사풀이었고, 잘 모르겠다고 해서 같이 고민했습니다. 얼마 안지나서 저와 firstin0907이 동시에 N+N/2+...+N/N & 이분탐색 풀이를 떠올리는데 성공했습니다. 30만 로그제곱이 불안해서 로그를 떼는 방법도 고민해봤고, 카운팅배열로 어렵지 않게 NlogN 풀이가 가능하다는걸 캐치했습니다. 코드도 굉장히 짧아서, B에 머리를 박던 andrewmjk1가 화장실에 간 사이 후다닥 짜서 제출했고, 한번에 맞췄습니다.

B WA [-4] (122min)

B WA [-5] (126min)

E AC [+] (140min)

 

andrewmjk1이 자리에 돌아오고 얼마 지나지 않아 뭔가를 고쳐서 결국 B도 AC를 받아냈습니다.

B AC [+5] (149min)

 

30분가량 남은 시점,  H와 J가 남았습니다. andrewmjk1이 H는 트리 DP로 해결할 수 있다고 해서 머신을 넘겨주고 저도 H를 고민해 봤습니다. 가만 보니 제한이 작아서 모든 리프 쌍의 경로를 고려해도 되고, 심지어 경로의 길이가 최대 20정도라 그냥 쌩 나이브를 짜도 될거 같았습니다. 제가 머신을 뺏어오고 두 팀원들이 옆에서 페어코딩하면서 열심히 구현했습니다. 예제가 안나와서 print디버깅 10분정도 하다가 고치는데 성공하고 예제가 나오길래 제출했지만 WA를 받았습니다.

H WA [-1] (171min)

 

실수한 부분이 하나 있어서 고치고 다시 제출했지만 또 WA를 받았습니다.

H WA [-2] (175min)

 

결국 H를 해결하지 못한 채로 대회가 종료됐습니다. 

---

 

대회가 끝나자 마자 H 출제자가 와서 놓친 케이스 하나를 알려줬습니다... 10분정도만 더 있었으면 풀 수 있었을거 같은데, 정말 아쉬웠습니다.

 

 

대회 종료 시점의 프리즈된 스코어보드입니다. 1등팀이 프리즈 이후 적어도 C와 H 2솔브는 했을 것 같았고, 1솔브라고 하더라도 패널티 차이로 져서 일단 1등은 물건너갔다고 생각했습니다. 게다가 제가 생각했던 것 보다 잘하는 팀이 훨씬 많았고, 어쩌면 수상권에 들 수 없을수도 있겠다 싶었습니다.

 

 

정말 아쉽게도 동일 8솔브에 패널티 차이로 2등을 하게 됐습니다. 1등팀이 당연히 H를 풀었을거라 생각했는데 WA인걸 보고 진짜 대회장 의자에 쓰러졌었습니다. H가 보기에만 무섭지 별로 어렵지 않은 문제였어서 아쉬움이 정말 컸습니다.

 

프리즈 이전 2,3등팀은 프리즈 이후 1솔브로 그쳤고, 오히려 6등팀이 프리즈 이후 3솔브를 해내면서 3등까지 올라온게 놀라웠습니다. A에 17트 인간승리와 H 유일솔브는 정말 멋있다고 생각합니다.

---

뭔가 팀대회 나갈 때 마다 패널티 쌓는 귀신이 되는거 같은데... 실수 줄이고 긴장 덜 하는게 1순위 과제인 것 같습니다.

어쨌든 아쉬움도 많지만 그래도 나름 나쁘지 않게 친거 같네요. andrewmjk1 빡캐리 감사합니다.

오랜만에 팀대회도 해보고 학교 사람들 만나서 PS이야기 ICPC이야기 들으니 갑자기 저도 팀 구해서 막 연습하고 대회 나가고 싶은 욕구가 스멀스멀 올라옵니다. 물론 군대부터 다녀와야겠지요...

대회 준비해주신 ALOHA 운영진들과 참가자분들, 특히 저희 팀원분들 정말 수고하셨습니다!

BetterthanO1 아챔진출을 기원하면서 글을 마치도록 하겠습니다.