South American Qualifiers

남아 있는 팀들의 앞으로 얻어야 하는 승점만 상태로 저장한다.

현재 $m$개 팀이 남아 있고, 이들이 서로 치를 경기에서 앞으로 얻어야 하는 승점을 정렬한 상태를

$$(a_1,a_2,\cdots,a_m)$$

이라고 하자. 팀의 이름은 이후 판정에 영향을 주지 않으므로 상태를 항상 정렬해도 된다.

한 팀 제거

한 팀을 골라 그 팀이 나머지 $m-1$개 팀과 치르는 모든 경기 결과를 먼저 정한다. 선택한 팀이 상대에게 이기면 선택한 팀은 3점, 상대는 0점을 얻는다. 비기면 양쪽이 1점씩 얻고, 선택한 팀이 지면 선택한 팀은 0점, 상대는 3점을 얻는다.

선택한 팀의 목표 승점이 $x$라면, 이 $m-1$경기에서 선택한 팀이 정확히 $x$점을 얻는 배치만 고려한다. 각 상대 팀의 목표 승점에서는 이번 경기에서 그 상대가 얻은 점수를 빼 준다. 그 뒤 선택한 팀을 제거하면, 남은 $m-1$개 팀은 다시 같은 형태의 완전 라운드로빈 문제가 된다.

따라서 다음 재귀가 정확하다.

• $m=0$이면 가능하다.
• $m=1$이면 남은 목표 승점이 0일 때만 가능하다.
• 한 팀을 골라 그 팀과 다른 팀들의 경기 결과를 가능한 모든 방법으로 배치한다.
• 상대 팀들의 남은 목표 승점을 갱신한 뒤 선택한 팀을 제거하고 재귀한다.

정당성

실제 가능한 경기 결과가 하나 존재한다고 하자. 어떤 팀을 선택하더라도 그 실제 경기 결과에서 선택한 팀과 나머지 팀의 $m-1$경기 결과를 그대로 취하면 재귀가 열거하는 경우 중 하나가 된다. 그 결과를 빼고 선택한 팀을 제거하면 남은 팀들끼리의 실제 경기 결과가 그대로 더 작은 문제의 해가 된다. 따라서 가능한 경우를 재귀가 놓치지 않는다.

반대로 재귀가 어떤 경기 결과 배치를 선택하고 더 작은 문제에서도 성공했다면, 선택한 팀의 경기 결과와 재귀에서 얻은 남은 팀들의 경기 결과를 합치면 현재 $m$개 팀의 모든 경기가 정확히 한 번씩 정해지고 모든 팀이 목표 승점을 얻는다. 따라서 재귀가 성공한 경우는 실제로 실현 가능하다.

상태 정규화와 메모이제이션

팀의 이름은 중요하지 않으므로 상태를 정렬한 뒤 메모이제이션한다. 같은 잔여 승점을 가진 상대 팀들은 서로 구별할 필요가 없다. 따라서 같은 점수를 가진 상대들을 하나의 그룹으로 묶고, 그 그룹에서 몇 팀에게 이기고, 몇 팀과 비기고, 몇 팀에게 질지만 열거한다. 이렇게 하면 동일한 배치를 여러 순열로 중복 탐색하지 않는다.

분기 수를 줄이기 위해 가능한 $(W,D,L)$ 조합의 수가 가장 적은 팀을 먼저 제거한다. 여기서 $W+D+L=m-1$이고 $3W$이다.

필요조건 가지치기

재귀 상태에서 다음 조건들을 빠르게 검사한다.

• 한 팀이 $g=m-1$경기에서 얻을 수 있는 점수는 어떤 $W,D,L \geq 0$에 대해 $W+D+L=g$, 를 만족해야 한다.

이 조건들은 모두 필요조건이므로, 하나라도 실패하면 해당 상태는 즉시 불가능하다고 판정할 수 있다.

팀의 수 10은 고정되어 있다. 정렬된 잔여 승점 상태를 전역 메모이제이션하면 서로 다른 테스트 케이스도 많은 하위 상태를 공유한다. 따라서 주어진 $T\leq 200$ 범위에서 충분히 빠르게 동작한다.

Solution written by GPT5.6