백준 13560번: 축구 게임

팀의 수 n과 n개의 팀 각각의 승리 횟수가 주어졌을 때, 유효한 횟수인지 아닌지 찾는 문제.

2016 대전 ACM-ICPC 본선에 나온 문제이다.

예를 들어 n이 4이면,

0 2 1 3과 같은 승리 횟수는 가능하지만

0 3 3 0과 같은 승리 횟수는 불가능하다. 한 팀이 3회 이기면, 다른 팀은 무조건 패가 하나는 생기기 때문에 3이 또 올 수 없기 때문이다.

이 문제는 사실 잘 알려진 문제이다.

모든 팀이 서로 다른 팀들과 경기를 할 때 생기는 그래프를 Tournament 그래프라고 한다.

tournament 그래프의 score sequence가 유효한지를 알아내는 정리로 Landau's Theorem이라는 것이 있다.

score sequence를 non-decreasing하게 재배치한 뒤(=정렬), 각각을 $s_1$, $s_2$, ..., $s_n$이라 했을 때

i) $s_1 + s_2 + ... + s_i >= \binom{i}{2}$ for every $1 \le i \le n - 1$

ii) $s_1 + s_2 + ... + s_n = \binom{n}{2}$

이 두 식이 score sequence가 유효하기 위한 필요충분조건이다.

왜 이런 허무한 조건이 성립할까?

먼저 필요 조건이 성립함은 쉽게 알 수 있다.

n개의 팀 중 임의로 i개의 팀을 골랐을 때, i개의 팀 사이에서는 자기들끼리 $\binom{i}{2}$번의 경기가 벌어지고 경기마다 승자가 한 명씩 생기므로 승리의 합이 $\binom{i}{2}$ 이상이어야 한다. 정렬한 상태에서 가장 작은 i개의 수에 대해 i)번 식이 성립하면 다른 모든 임의의 i개의 팀 사이에서도 i)번 식이 성립함은 자명하다.

또한 총 승리의 횟수가 $\binom{n}{2}$여야 하는 것은 너무나도 자명하다.

문제는 왜 이것이 충분조건이냐는 것인데, 이는 증명이 꽤나 까다롭다.

https://ajc.maths.uq.edu.au/pdf/20/ocr-ajc-v20-p19.pdf

이런 곳에 증명이 나와 있다.

이런 문제는 대략 정리를 알고 있으면 아주 쉽게 풀 수 있는 문제, 그렇지 않다면 적당히 때려맞추어야 하는 문제에 가깝다고 생각된다.

내가 별로 안 좋아하는 유형.