2024 ICPC Korea regional 인터넷 예선 후기

오랜만입니다. 리유나입니다.

 

이번 토요일에 2024년 ICPC 서울 리저널에 참가했습니다. 팀은 재작년, 작년과 마찬가지 인원의 문송송 계란탁이지만, 이번에 바뀐 ICPC 팀명 정책으로 인해 MunSongSong Eggdrop이 아닌 "Gyerantak"으로 출전했습니다.

 

0. 스코어보드

아실분들은 아시겠지만, 스코어보드가 두 버전이 있습니다()

이쪽이 대회때 보인 스코어보드였고

이쪽이 실제 스코어보드입니다.... 무슨 일이 있었는지는 차차 설명토록 하겠습니다.

 

1. 타임라인

대강의 대회 타임라인은 다음과 같았습니다.

 

(0분) 제가 앞부분, songC가 중간, mhy가 뒷부분을 봤습니다. 앞에 있는 문제들이 전부 영 풀만해 보이는 건 없어서 조금 고민이었습니다. 그나마 가능성 있어보이는 건 D였어서 D의 풀이를 생각하기 시작했습니다.

 

(6분) songC가 E가 쉽다고 해 곧바로 구현에 들어갔고 이후 AC를 받았습니다.

 

(18분) 잇달아 songC가 H를 AC 받았습니다.

 

(33분) F 역시 백트래킹으로 잘 구현하면 되는 크게 어렵지 않은 문제였기에 바로 AC를 받았습니다. 아마 이 시점까지는 스코어보드에서 여유롭게 1등을 하고 있었던 걸로 기억합니다.

 

...그리고 대참사가 벌어졌습니다.

 

(60분 언저리부터..?) mhy가 C를 잡고 풀기 시작했습니다. 해싱이나 그래프 치환 이후 다익스트라 등 여러 방법을 고민해보다가, 문제 이해를 잘못한 걸 깨닫고 다시 구현하다가, 그러다가 예제들이 잘 나오지 않아서 다시 구현하다가, 틀린 거 같아서 코드 프린트 후 다시 구현하다가, 등등 수많은 시행착오 끝에도 AC가 나올 기미는 보이지 않았습니다. 저와 songC는 mhy가 말렸다고 판단, 다른 문제들부터 차라리 생각할 것을 제안했습니다.

 

(91분) D의 AC를 받았습니다. 처음에는 정말 binary matrix를 이용해서 2000원연립1차방정식을 풀어야 하나...하는 생각을 했습니다. 영향을 끼칠 수 있는 것들이 한 변수에 많아야 두개니깐 식이 생각보다 예쁘게 나오지 않을까 같은 생각을 했는데 이건 역시 에바인 거 같아서 songC와 의논한 결과 2-SAT이나 더욱 간단히는 유니온 파인드로 관리 하면서 바로 가능하다는 풀이를 도출해내고 구현해 맞았습니다.

 

이후로 mhy는 C, 저는 K, songC는 G에 사활을 걸고 구현했지만 모두들 구현이 크게 막히면서 굉장히 진행이 답보되었습니다. 저희는 정말 이 시점에서 이대로면 본선 수상과 월파는커녕 애초에 본선 진출도 위험하다고 생각해서 크게 긴장하며 마음을 졸이고 있었습니다.(결론적으로 이 시점에서 대회가 끝나도 본선 진출은 가능했으니 기우였지만요 ㅋㅋ)

 

이윽고 모두가 멘탈이 나간 2시간 반 이후 시점즈음부터, 저는 어떻게든 K 풀이 구상을 마쳤고, songC는 G의 디버깅이 거의 끝나가는 듯했습니다. 그래도 4솔로 대회를 끝낼 수는 없었기에 마지막까지 최선을 다했습니다.

 

(169분) 기적적으로 songC의 G 풀이가 AC를 받았습니다.

 

(175분) 무려 종료 겨우 5분을 남기고서, 저의 K 디버깅이 끝나고 풀이가 AC를 받았습니다.

 

이후 mhy는 C를 계속 보고 있었지만 결국 틀린 점은 찾지 못하고, 대회는 끝나고 말았습니다. 대회가 거의 끝날 즈음에, mhy가 "아니 나 배열을 20만까지로 해야 하는데 10만이라고 해서 런타임 에러가 떠야 하는데? 왜 WA가 뜨지? 아예 구현 자체를 잘못했나?"하는 발언이 나왔고, 이 발언이 이후 일어날 사태의 복선이 되었습니다.

 

희한하게도 이번 대회는 프리즈가 없었기에 결론적으로 당시 스코어보드 7위였고, 그대로 본선 진출을 확정짓고 후련하게 대회를 마쳤습니다.

 

2. 대회 이후의 일들

다음 날 갑자기 팀원들과의 톡방에서 C에 대해서 AC를 받은 코드들의 반례가 속출/애초에 데이터가 틀린 것 같다는 이야기 등이 나오기 시작했습니다. 어차피 저희야 틀린 문제니 신경을 안 쓰고 있었지만, 여기저기서 노이즈가 심심치않게 들리더라고요.

 

또한 공지사항에서의 수정 사항을 순위표를 내리고 재채점이 이루어지고 있다고 나와서, 문제가 된 건 C가 맞겠구나하고 다들 반쯤 확신하는 분위기였습니다.

 

이후 C의 문제 오류가 있었던 것이 정말로 확인되었고, 기존 C가 AC였던 팀은 정답 인정/기존 C가 AC가 아니었지만 재채점 이후 AC가 된 팀은 정답 인정+본선 무조건 진출, 이후 팀 선발을 추가적으로 진행한다는 규칙 하에 본선 선발 팀을 선정한다는 공지가 올라왔습니다. 순위표 또한 대회 당시의 순위표(첫번째 사진)과 재채점 이후의 순위표(두번째 사진)이 모두 올라오게 되었습니다.

 

3. 푸념

결론적으로 예선 등수야 정말 사실 아무 상관도 없고, 본선 진출은 어떤 버전의 순위표이든 아주 여유롭게 하니까 별 상관은 없다 싶지만, 역시 너무나도 아쉽고 실망스러운 것도 사실입니다.

 

저희의 C 코드는 알고리즘은 옳았으나 배열 선언 길이가 잘못되어서 원래대로라면 runtime error가 나와야 하는 코드였습니다. 그렇지만 WA가 나와서 알고리즘 자체가 틀렸다고 생각하고 쭉 디버깅하다가 오류를 찾지 못해서 결국 틀리게 되었습니다. 틀린 데이터가 없이 RE가 결과로 나왔다면, 디버깅의 방향성은 알고리즘 구조보다는 배열 선언과 인덱스 등에 집중되었을 것이므로 어렵지 않게 디버깅할 수 있었을 거라는 생각이 듭니다.

사실 저희야 C의 정답 유무가 별 영향을 끼치지 않는 등수권의 팀이었지만 이런 이유로 C를 충분히 풀 여력이 있었음에도 풀지 못한 팀이 또 없었으리라는 보장은 없습니다. 결과적으로 재채점 이후 AC를 받은 팀들은 구제를 받았지만, 이런 경우는 결국 증명하기도 어렵고, 증명한다 하더라도 처리하기도 어렵다는 점은 간과할 수 없습니다. 애초에 이런 사태가 벌어지게 된 것이 굉장히 유감스럽다고 생각합니다.

 

실은 잘 알려지지는 않았지만, 지난해 ICPC 예선의 H번 Rigged Lottery 문제에서도 잘못된 데이터가 있었습니다. 이 데이터의 문제는 데이터 뒤로 들어와서는 안될 더미 데이터들이 붙어있는 상태로 계속 입력이 들어온 것이었고, 사실 대회 중 AC를 받은 팀이 한 팀뿐이었고 C++을 이용해서 입력을 받는다면 보통은 문제가 없다 판단하고 풀 수 있는 상태인 것은 맞습니다. 그러나 제가 이후 업솔빙을 할 때 Python으로 줄 입력을 받고 split하는 식으로 진행했을 때는 예상한 것보다 변수가 많이 들어와 알고리즘이 꼬여 잘못 풀게 되었고, 아무리 생각해도 이 방식이 틀린 것 같지 않아서 대회 공식 제공 데이터를 받아보고서야 굉장히 허탈한 기분을 느끼게 되었습니다. 실제로 제가 작년 예선에서 이 문제를 보고 있었으니, 만일 작년의 제가 이 문제를 풀고 제출했는데 WA를 받고, 한참 뒤에야 그 이유를 이렇게 알았더라면 굉장히 화났을 것입니다.

 

아무쪼록 저는 올해를 끝으로 ICPC에 출전하지 않지만, PS와 CP를 좋아하는 사람으로서, 그 매력에 큰 상처가 될 수 있는 이런 일이 본선에서는 절대로, 그리고 이다음부터는 다시는 재발하지 않기를 진심으로 바랍니다.

 

저 또한 마지막 ICPC 본선에서 후회 없을 정도로 불태우고 모든 것을 쏟아붇고 돌아오겠습니다!

 

4. 문제별 풀이 간략 정리

스포일러가 될 수 있으니 원치 않으시다면 바로 내려주시기 바랍니다.

 

A. 정말로 깡.구현.문제. 교차하는 점들을 잘 찾아주고 시뮬레이션을 돌리면 되는 문제입니다. 저희 팀은 이런 거 짤 시간 없다고 넘겼습니다.

B. BST를 주어진 순서대로 앞에서부터가 아니라, 반대로 뒤에서부터 하나씩 채워 넣는데 항상 마지막에 채워진 수가 root node가 되어야 한다는 규칙을 따른다 생각해보면, 마지막에 채워지는 노드 k에 대해서 u-v가 이어져있고 u<k<v 혹은 v<k<u를 만족하는 엣지들만이 끊어집니다. 몇개의 엣지가 끊어지는지 값을 잘 기록해 두면 문제를 풀 수 있습니다...만, 구현이 상당히 복잡할 것으로 판단되어 대회 중에 구현하지는 않았습니다.

C. 문제의 그 문제입니다........ 롤링 해싱으로 부분문자열 판별하게 해주고 prefix가 얼마나 겹치는지를 판단할 수 있습니다. DP를 통해서 전이를 관리하면 된다고 합니다.

D. 위에서 언급한 유니온파인드로 관리하는 방법이 있고, 혹은 그냥 DFS로 싹다 돌아봐도 괜찮다고 합니다. 정해는 후자에 가깝지 않을까 싶습니다.

E. 그냥 하면 됩니다.

F. 두 지역 사이의 선 개수가 홀수인지 짝수인지에 따라 달라집니다.

G. 임의의 MST를 하나 잡고, 거기에 들어가지 못한 간선에 대해, 그 점 두개를 연결하는 mst 상 경로에 같은 가중치를 가진 간선이 있다면 타입 2, 없으면 타입 3. 이미 트리에 들어간 간선들에 대해서는 밖의 간선들의 경로로 자신을 덮을 수 있는, 자신과 같은 비용의 간선이 있는지를 체크해서 없으면 1, 있으면 2가 된다고 합니다. songC는 작은 집합에서 큰 집합으로 합치는 테크닉으로 어떻게 잘 했다고 합니다.

I. 인터랙티브. 각 사분면들에 대해서 따로 한다는 느낌으로 잘 해주면 된다고 합니다. 뭐 이분탐색을 여차저차 잘하면 된다고...는 하는데 대회 중에 구현한 것도 아니고, 풀이만 나오고 던진 문제라 정확히는 모르겠습니다.

J. 두 고리가 어떤 선을 기준으로 갈라지는지를 먼저 생각하고, 조건 잘 걸고 이분탐색으로 잘 하면 된다고 합니다.

K. 이상한 기계와 이상한 언어를 가지고 정렬하는 코드를 직접 짜야 되는 기가 막힌 형식의 문제였습니다. 제 방법은 '흰공과 파란공들의 집합은 모두 뭉쳐있다'는 점을 최대한 유지하면서, 임의의 파란 공을 잡아서 '빈 구간'의 오른쪽 끝으로 옮기고, 반대편에서 보이는 걸 바로 빈칸에 넣어주고...를 반복하면 언젠가는 정렬이 된다는 점입니다. 처음에는 무조건 n번 이 행위 후에 정렬이 보장된다고 하면 exit하는 식으로 하려고 했으나 그렇게 n번 카운트<<자체가 어려운 언어였기 때문에, 무한루프를 돌되 정렬됨이 판단되면 바로 exit하는 식으로 구현했습니다.