2024 ICPC Asia Seoul Regional 후기

팀원 : abra_stone, gs20036

 

별로 후기글을 쓸 만큼 좋은 성적을 거두지 못한 대회라 짧게 쓰고자 한다.

 

예선) A, E, F, H를 풀었다. 나는 빠르게 E와 F를 풀고, 남는 시간에 G 풀이를 냈다. gs20036이 A를 퍼솔하고 abra_stone이 H를 맞왜틀 끝에 풀었는데, 남은 시간에 gs20036의 D와 내 G를 둘 다 짜려다가 둘 다 맞왜틀을 당하고 4솔로 마무리했다. 내가 푼 문제들의 풀이는 다음과 같다.

 

E : 각 열에 대해 전처리를 하면 된다. 매우 쉬운 문제이다.

F: 각 선분에 대해 주어진 두 점이 같은 편에 있는지 반대편에 있는지 판별하면 된다. 이는 CCW를 이용해 쉽게 할 수 있다.

G: 같은 가중치를 가진 간선들을 그룹화하고 가중치가 작은 순으로 정렬한다. 이후 크루스칼 알고리즘을 생각하자. 같은 가중치를 가진 간선 중 무엇을 먼저 보느냐에 관계없이, 한 그룹의 모든 간선을 다 본 시점에 그래프의 연결 성분 정보는 유일하게 결정된다. 따라서, 가중치가 작은 그룹부터 보면서 다음을 반복하면 된다. 초기에 $find(i) = i$이고, 현재 보고 있는 그룹이 $S$라고 하자.

1. 모든 정점 $i$에 대해 $find(i)$만을 남긴다.
2. $S$의 모든 간선 $uv$에 대해 $find(u)$와 $find(v)$ 사이에 간선을 추가한다.
3. 이후 $find(u)find(v)$가 단절선이면 $uv$는 1번, 루프면 $uv$는 3번, 그 외에는 $uv$는  2번이다.
4. $S$의 모든 간선 $uv$에 대해 $find(u)$와 $find(v)$를 union한다.

본선) A, B, F, J, L을 풀었다. 나는 B와 L을 풀었고, 누가 A를 풀었는지는 잘 기억이 나지 않는다. J는 gs20036이 쉬운 문제라고 잡았는데 자꾸 맞왜틀이 나서 abra_stone이 그냥 다시 짜서 맞았다. 그리고 이 후기글의 주인공인 F는...

 

대회가 시작하고 2시간이 지나기도 전에, gs20036이 F를 제출했다. 그러나 WA가 떴고, 이전에 J에서 3틀을 했기에 오늘 gs20036의 구현 폼이 안 좋다는 것을 봤던 나와 abra_stone은 어딘가 구현 실수가 있을 것이라고 생각했다. 그래서 코드를 프린트시킨 후 디버깅을 하는 동안 abra_stone이 J를 다시 짰다. 이후 128분에 abra_stone이 다시 구현한 J로 AC를 받자 우리는 우선 F를 푸는 것에 집중하기로 했다. 스코어보드 상태를 보았을 때 수상을 위해서는 A, B, F, J, L이 기본인 것 같았기 때문이다.

 

그런데 gs20036의 말로는 코드에 아무리 봐도 이상이 없다고 했고, 가능한 데이터가 최대 100개도 안되는 문제였기에 급기야 체커와 제너레이터를 짜서 모든 테스트케이스에 대해서 맞는 코드라고 주장했다. 하지만 직전에  J에서 gs20036이 짠 코드를 갈아엎고 abra_stone이 짜서 맞은 전적이 있었기에 우리는 믿지 못하고 내가 다시 코드를 짰다. 그러나 또 WA가 떴고, 내 코드에 대해서도 모든 데이터에 대한 테스팅을 진행했다. 하지만 또 로컬에서 모든 데이터가 통과해버렸다. 뭔가 이상함을 느낀 우리는 다같이 디버깅을 시작했다. 그러나 아무리 봐도 버그를 찾을 수 없었고, 대체 어떤 데이터에 대해서 틀리는지 제출을 통한 탐색이라도 해보기로 했다.

 

$n=3$일 때만 런타임 에러를 내는 코드를 제출한 결과, 첫 데이터는 $n=3$이며 우리의 코드는 $n=3$일 때부터 제대로 작동하지 않는다는 사실을 발견했다. 심지어 $n=3$일 때의 예제 출력을 그대로 출력해도 제대로 작동하지 않았다. 설마 설마 하면서 출력의 마지막에 개행을 추가했는데, 드디어 런타임 에러가 나지 않았다. 그제서야 우리는 문제의 체커가 출력 형식에 관해 뭔가 우리의 예상과 다르게 작동하고 있다는 것을 확싱할 수 있었다.

 

그렇게 시행착오를 거쳐 알아낸 사실은, 각 줄의 맨 뒤에 있는 공백 하나가 말썽이었다는 사실이다. 즉, 다음과 같은 코드를

for(int i=0;i<n;i++){
	for(int j=0;j<3;j++) printf("%d ", arr[i][j]);
    printf("\n");
}

아래와 같이 수정하면

for(int i=0;i<n;i++) printf("%d %d %d\n", arr[i][0], arr[i][1], arr[i][2]);

해결되는 문제였다.

 

이렇게 AC를 받은 시점이 대회가 시작하고 4시간이 지난 시점이었다. 혹시나 해서 처음 제출한 코드에서 저 공백 이슈만 바꿔서 제출해봤는데, AC를 받았다. 즉 저 공백 하나 때문에 2시간 넘게 모든 팀원이 아무것도 못하고 있었던 것이었다. 다른 것도 아니고 체커의 억까를 겪고 나니 셋 다 더이상 대회를 칠 마음이 없었고, F를 디버깅하는 동안 풀이가 나왔던 C라도 짜보다가 던졌다.

 

대회가 종료된 후, 운영 측에 관련 이슈에 대한 클레임을 전달한 결과 받은 답변은 다음과 같았다.

1. '한 줄'은 당연히 줄의 마지막에 있는 개행 문자를 포함한다. 따라서 개행 문자가 없는 출력은 WA가 정당하다.
2. 세 수를 공백으로 구분하여 출력하라고 하면 세 수 사이에만 공백이 있는 것이 상식적이다.
3. 대회 전에 교수님들과 출력 형식에 관해 논의한 적이 있고, 체커가 그렇게 동작하는 것은 의도된 사항이다.
4. 만약 다른 문제의 체커가 줄 끝의 공백 등을 허용해준다고 해도, 그 문제가 아량을 베푼 것이지 이 문제의 체커도 그렇게 동작해야 한다는 근거는 되지 못한다.

따라서 체커는 의도대로 동작했고, 대회에 문제가 없었다는 답변이었다. 또한 PS 대회에서 사소한 환경 차이를 예측하고 적응하는 것 역시 경험에서 나오는 실력 중에 하나라는 이야기도 들었다. 사실 체커에 관한 규칙이 공지되지 않았었기에, 교수님들이 의도한 사항이라는 점 하나만으로도 우리가 이의를 더 제기할 수 있는 부분은 없었다.

 

그러나 개인적으로 의아한 것은, 보통 이런 대회는 상위 대회의 규정을 따르지 않나 하는 것이었다. 물론 리저널은 각 국가에서 알아서 진행하는 것이 맞지만 따로 공지하지 않은 규칙에 대해서는 월드 파이널의 규정을 따라야 한다고 생각한다. https://docs.icpc.global/wp-content/uploads/2024/08/2024-JudgingNotes.pdf 에 따르면 줄의 끝에 있는 공백은 허용되는데, 그렇다면 교수님들은 월드 파이널의 체커가 비상식적이라고 생각해서 리저널에서라도 상식적인 체커를 짜고 싶으셨던 것일까.

 

PS에 if란 없다는 말이 있지만, 만약 줄 끝의 공백이 허용되어 F를 첫 제출에 맞았다면 우선 5솔 중에는 1등이었고, 정해 풀이를 낸 C까지 맞춘다면 높은 확률로 25등이었다. 남은 시간에 한 문제를 더 푸냐 마냐로 수상권을 노려볼 수도 있는 대회였는데 참 아쉬운 경험이었다. 아무리 잘했어도 아챔 진출권은 아니었다는 게 그나마 위안 삼을 만한 점이었던 것 같다.

 

아래는 내가 푼 문제들의 풀이이다.

B: 색깔을 정점으로, 카드를 간선으로 생각하자. 이렇게 구성된 그래프의 각 연결 성분에 대해, 웬만하면 모든 색이 등장 가능하고 트리일 때만 색 하나가 등장 불가능하다는 것을 알 수 있다. 따라서 답은 전체 색의 개수에서 트리의 개수를 빼면 된다.

L: 한 변에서 애매하게 중간에 있는 점을 골랐다고 해보자. 그러면 해당 점 대신 그 변에서 고를 수 있는 양쪽 끝 점 중 하나를 골랐을 때, 적어도 한 번은 삼각형의 넓이가 작거나 같아진다. 따라서 답은 세 변 모두에서 양쪽 끝 점 중 하나를 고른 8가지 삼각형 중에 하나이다.