BaaaaaaaarkingDog
코딩, 해킹
ICPC 아시아지역 WF teams 선정 규칙


의외로 ICPC World Finals에 진출할 팀을 어떻게 선정하는지에 대한 정보가 부족해 아시아 지역 디렉터 C.J. Hwang님의 블로그를 정말 열심히 뒤져서 선정 규칙을 한 90%는 이해했다. 절차를 소개하기 전에 배경 지식을 몇 가지 소개하고 가겠다.

  1. 아시아 지역은 EC and China, WC and India, Pacific & SE Peninsula 총 3개의 구역(sub-region)으로 나누어진다. 보통 EC, WC, PSP 라고 많이들 표기한다.
  2. 한국은 PSP 지역에 속해있고, 세 구역의 순위 산정 방식은 모두 다르다.
  3. 아시아에서 WF에 진출하는 팀은 총 45개 팀이다.(이건 규정에 명시된 것은 아닌데, 언젠가부터 늘 45개 팀이었다.)
  4. 각 팀은 최대 2개의 Regional에 참여할 수 있다.
이제 45개의 WF 슬롯을 각 지역에 어떻게 배분하는지 알아보자.
  • 우선 작년 WF에서 메달을 딴 팀에게 우선적으로 슬롯을 준다. 2018년 WF를 기준으로 한다면, EC에서 Peking University, Tsinghua University, Shanghai Jiao Tong University가 메달을 땄고 PSP에서 The University of Tokyo, Seoul National University가 메달을 땄으므로 5개의 슬롯은 이미 가져가는 대학이 정해져있는 상황이다.
  • 0-6개의 슬롯(단, 0-6이 규정상에 명시된 값은 아니다.)이 여러 복합적인 상황들로 미리 몇 개의 대학에 할당된다. 예를 들어 내년에 WF를 호스팅하는 팀이라던가, Regional을 10년 넘게 진행한 팀이라던가, 이때까지 WF에 한번도 진출을 하지 못한 국가에서 Regional에 출전했는데, 자력으로 WF에 진출하지는 못했지만 좋은 성과를 보여줬다거나 하는 이유가 있다. 한국에서는 대전 리저널을 오랫동안 담당한 카이스트나 앞으로 서울 리저널을 담당할 것으로 보이는 세종대에서 이 혜택을 받을 가능성이 있다.
  • 남은 슬롯을 EC, WC, PSP에 분배한다. 이 때 리저널 참여도와 WF 성적을 기준 삼아 분배가 이루어진다. 보통 EC > WC > PSP 순으로 분배가 일어난다. 2016년 WF에는 PSP가 31장 중에서 9장, 2017년 WF에는 38장 중에서 11장, 2018년 WF에는 35장 중에서 9장을 할당받았다.
이렇게 PSP에 분배된 n장의 슬롯을 각 리저널 결과로부터 어떻게 정해지게 되는지를 알아보자. 2018년 기준으로 PSP 지역에는 총 8개의 Regional이 있다. 그리고 각 Regional의 점수는 아래의 5가지 항목으로부터 정해진다.
  • 적어도 한 문제를 해결한 참가팀/참가대학의 수가 많으면 많을수록 Regional의 점수는 증가한다.
  • 참가팀 중 2개의 Regional에 참여한 팀이 많으면 많을수록 Regional의 점수는 내려간다.(홈페이지에 The Site Reduction Factors라고 명시가 되어있는데 정확한 계산 방식은 이해하지 못했다.)
  • max(외국팀의 수, 25) * 0.02 가 Regional의 점수에 추가된다.
  • Provincial and national contest에 참가한 대학의 수 또한 많으면 많을수록 Regional의 점수는 증가한다.(한국에는 이러한 종류의 대회가 존재하지 않는다.)
이제 이들을 바탕으로 Regional 점수를 계산하는데 참가 대학의 수를 70%, 참가 팀의 수를 25%, Provincial and national contest의 참가 팀의 수를 5%로 두어 Online, On-site 각각에 대해 계산해 Online을 20%, On-site를 80%로 두어 합산한다고 적혀있다. 뭘 어떻게 한다는건지 적혀있는 규칙을 보아도 잘 이해가 가지 않는다.

아무튼 이렇게 복잡한 과정을 거쳐 Regional 점수가 계산되고 나면, 비로소 대학의 우선순위가 결정하는 법을 알 수 있게 된다. 편의상 작년(=2017년) 리저널 결과를 가지고 설명을 하겠다.(링크 참고)

작년에는 8개 지역에서 리저널이 개최되었고 리저널 점수를 추정해보면 아래와 같다.
  • 호치민(베트남) 리저널 : 2.36
  • 자카르타(인도네시아) 리저널 : 1.73
  • 대전(한국) 리저널 : 1.69
  • 츠쿠바(일본) 리저널 : 1.22
  • 나콘빠톰(태국) 리저널 : 1.02
  • 화련(타이완) 리저널 :  1.01
  • 양곤(미얀마) 리저널 : 0.86 미만
  • 마닐라(필리핀) 리저널 : 0.86 미만
작년의 경우 자카르타/호치민 리저널 3등이 양곤/마닐라 리저널 2등보다 우선순위가 높았고, 호치민 리저널 4등이 자카르타, 대전 리저널을 제외한 나머지 리저널 3등 보다 우선순위가 높았다.


리저널의 등수는 자신보다 등수가 높은 대학의 수 + 1이다. 예를 들어 특정 리저널에서

A대학 a팀 - 1위

A대학 b팀 - 2위

B대학 c팀 - 3위

C대학 d팀 - 4위

B대학 e팀 - 5위

를 기록했다면, a b팀은 해당 리저널에서 1위를 한 것이고 c팀은 2위, d e팀은 3위를 했다고 생각하면 된다. 추가적으로 리저널의 등수를 산정할 때 PSP지역이 아닌 대학(중국 혹은 홍콩 혹은 인도 등등), 작년 WF에서 메달을 획득한 팀은 애초에 스코어보드에 없다고 가정하면 된다.


리저널 점수가 S인 곳에서 R위를 한 팀은 (R-1) / S라는 페널티를 가진다. 해당 페널티가 작은 순으로 팀들을 골라 WF에 진출시킨다. 위의 리저널 점수로 예를 들면, 호치민 리저널에서 2위를 한 팀은 (2-1)/2.36 = 0.423의 페널티를 가지고, 대전 리저널에서 3위를 한 팀은 (3-1)/1.69 = 1.183의 페널티를 가진다.


링크를 보면 알겠지만, 페널티 순으로 9개의 대학이 정해질 때 까지 잘랐는데 그 명단에 대학이 동일한 팀이 존재할 경우 해당 대학의 코치가 어느 팀을 진출시킬지 정한다. National Taiwan University, National University of Singapore 등등이 리저널 4-5개를 쓸어먹기 때문에 이런 상황이 굉장히 자주 발생하고, 더 나아가 계속 내려가다보니 2017년 WF에는 자카르타 리저널에서 4위를 기록한 Universitas Indonesia 대학 팀이 진출하기도 했다.


규정을 찾아보면 볼수록 정말 난해하고 불명확한게 많다는 생각밖에 안든다. 그리고 C.J. Hwang님의 블로그가 너무 난잡하다.

  Comments
댓글 쓰기