내 대통령이 아니다

wikimedia.org에서 가져온 이미지

2016 United States Presidential 선거가 끝난 뒤, 많은 사람이 대통령이 국민 과반수의 지지를 받지 못했다고 생각하여 시위했다. 전국 곳곳에서 ``NOT MY PRESIDENT''라는 말이 들렸다. 선거에서 Hillary Clinton는 득표수의 $48.2\%$를 얻었고, Donald Trump는 득표수의 $46.1\%$를 얻었다. 그럼에도 United States의 선거 제도 때문에 Trump가 승리했다.

Iceland에서는 득표수가 더 적은 후보가 가장 많은 표를 받은 후보를 이기는 것이 불가능하다. 우리의 선거 제도는 특별히 이 결함에 취약하지는 않지만, 완벽하다고 하기는 어렵다. Iceland의 선거 제도에서는 유권자가 투표할 후보 한 명을 선택하기만 하면 되며, 가장 많은 표를 받은 후보가 승리한다.

University of Iceland의 정치학 교수인 Ólafur Þórður Harðarson은 수십 년 동안 Iceland의 선거 제도를 비판해 왔다. 그는 오래된 글에서 특히 한 가지 결함에 관해 썼다. 그는 후보들 사이에 표가 거의 균등하게 분배될 가능성을 살펴보았다. 후보가 두 명이면 승자가 되기 위해 득표수의 절반을 조금 넘게 받아야 하므로, 이 제도는 가능한 한 공정해 보인다. 그러나 후보가 열 명 출마한다면, 당선되기 위해 득표수의 $10\%$를 조금 넘게 받는 것만으로 충분할 수 있다. 유권자의 첫 번째 선택만 고려되므로, 국민의 최대 $90\%$는 자신이 가장 싫어하는 후보를 대통령으로 맞게 될 수 있다.

흔히 비판받는 이 제도의 또 다른 결함은 사표로 알려져 있다. 선거 전에 실시되는 여론조사를 보면 어느 두 후보가 승리할 가능성이 가장 높은지 명확한 경우가 많다. 그 두 후보와 세 번째, 네 번째, 심지어 아홉 번째 순위 후보들 사이의 격차가 너무 커서, 어느 후보들이 상위 두 순위를 차지할지 여론조사에 명확히 드러날 수 있다. 그러면 유권자는 자신의 표가 상위 두 후보 간의 경쟁에 영향을 주지 못하므로 사표가 된다고 느낄 수 있다. 일부 유권자는 마음속으로는 차악을 선택한다고 생각하면서도, 상위 두 후보 중 자신이 더 좋아하는 후보에게 투표하기로 할 수도 있다.

이 문제의 한 가지 해결책은 모든 표가 영향을 미치도록 선거 절차를 여러 차례 진행하는 것이지만, Iceland와 같은 작은 나라에서는 재정적으로 실행 불가능할 수 있다. 다행히 단 한 차례만 진행하면 되고 앞서 언급한 결함이 없는 제도가 존재한다. 이 제도는 유권자가 선호도에 따라 후보들의 순서를 정하는 방식에 기반한다. 그러면 이 제도의 주된 결함은 유권자에게 투표 절차가 조금 더 복잡해진다는 점이다. 각 유권자의 첫 번째 선택이 선거의 초기 결과를 결정하며, 이는 현행 제도에서 얻는 결과와 같다. 차이점은 어떤 유권자도 득표수의 과반수를 보유하지 않은 동안에는 가장 적은 표를 받은 후보가 선거에서 제외된다는 것이다. 그 후보에게 주어진 표는 갱신되어 각 유권자의 다음 선택 후보가 그 표를 받는다. 어떤 후보가 득표수의 과반수를 보유하게 되면 선거의 승자가 결정된다.

Iceland 경쟁 프로그래밍 협회는 타임머신을 사용해 과거의 선거로 돌아가, 이 새로운 제도에서 어떻게 투표할 것인지 국민 모두에게 물었다. 협회는 천천히, 그러나 확실하게 시간을 거슬러 갔으며 모든 일이 순조롭게 진행되었다. 각 유권자는 모든 후보가 나열된 순서 있는 목록을 제공했다. 미래인 $2023$년으로 돌아갈 때가 되자 타임머신이 양방향으로 작동하지 않는다는 사실이 밝혀졌다. 따라서 협회 회원들은 Iceland에서 컴퓨터를 많이 찾아볼 수 없던 $1952$년에 발이 묶였다. 그러므로 그들은 새로운 표로 선거를 모의 실행하는 프로그램을 작성할 수 없었다. 그들은 다시 한번 $2023$년에 도달하기 위해 자신들을 냉동하기로 했고, Arnar는 누군가가 자신을 위해 프로그램을 구현해 주기를 바라며 이 지시 사항을 남겼다.

채점

그룹 | 점수 | 제한

1 | 25 | $m = 2$, $1 \leq n \leq 2\,000$

2 | 25 | $2 \leq m \leq 3$, $1 \leq n \leq 2\,000$

3 | 25 | $2 \leq m \leq 9$, $1 \leq n \leq 2\,000$

4 | 25 | $2 \leq m \leq 10^5$, $n \cdot m \leq 2 \cdot 10^6$

입력의 첫 번째 줄에는 공백으로 구분된 두 정수, 표의 수 $n$와 후보의 수 $m$이 주어진다.

다음 $m$개의 줄에는 각각 후보 한 명의 이름이 주어진다. 이름은 전부 영문 알파벳 문자로만 이루어진다. 각 이름의 글자 수는 $1$ 이상 $50$ 이하이다.

마지막으로 다음 $n$개의 줄에는 각각 하나의 표가 주어진다. 각 표는 $m$개의 정수, 즉 $1$부터 $m$까지의 수로 이루어지며, 각 수는 정확히 한 번씩 등장하고 유권자가 후보들을 선호하는 순서를 나타낸다. 따라서 줄의 첫 번째 수는 유권자의 첫 번째 선택 후보를 가리키고, 두 번째 수는 두 번째 선택 후보를 가리키며, 이후도 같은 방식이다. 수는 후보들이 입력에 등장하는 순서대로 후보를 가리킨다.

과정 중 어느 시점에서든 두 후보의 득표수가 같다면, 입력에 더 먼저 등장한 후보가 더 높은 순위인 것으로 간주한다.

선거 승자의 이름을 한 줄에 출력한다.