Разбор задачи «Выборы по системе runoff»

1. Идея

Нужно смоделировать процесс выборов раунд за раундом.

В каждом раунде:

• каждый бюллетень отдаёт голос самому предпочтительному кандидату из тех, кто ещё не выбыл;
• если кто-то набрал больше половины всех бюллетеней, он побеждает;
• иначе выбывает кандидат с минимальным числом голосов;
• если минимум одинаковый у нескольких кандидатов, выбывает кандидат с лексикографически наибольшим именем;
• если остался один кандидат, он побеждает.

То есть задача полностью сводится к аккуратной реализации описанных правил.

2. Наблюдения

Наблюдение 1. Удобно заменить имена на номера

Имена нужны для:

• чтения бюллетеней;
• сравнения при равенстве минимального числа голосов;
• вывода победителя.

Поэтому удобно:

• сохранить массив names, где names[i] — имя кандидата с номером i;
• завести словарь id_by_name, чтобы быстро переводить имя в номер.

Тогда каждый бюллетень можно хранить как список номеров кандидатов.

Наблюдение 2. Как определить голос бюллетеня в текущем раунде

В бюллетене кандидаты уже стоят в порядке предпочтения. Значит, достаточно пройти по нему слева направо и найти первого кандидата, который ещё не выбыл.

Именно он получает голос в текущем раунде.

Наблюдение 3. Кандидатов мало

По ограничениям m <= 20, это очень маленькое число. Значит, даже если в каждом раунде для каждого бюллетеня проходить по всем m позициям, это будет быстро.

Число раундов не больше m - 1, потому что в каждом раунде выбывает ровно один кандидат.

Наблюдение 4. Проверка победы

Нужно проверить, набрал ли какой-то невыбывший кандидат строго больше половины всех бюллетеней.

Это условие удобно записывать как:

• votes[i] * 2 > n

Так не нужно работать с вещественными числами.

Наблюдение 5. Разрешение ничьей на выбывание

Если несколько кандидатов имеют минимальное число голосов, выбывает кандидат с лексикографически наибольшим именем.

Значит, при поиске кандидата на выбывание нужно обновлять ответ не только когда голосов меньше, но и когда голосов столько же, а имя больше.

3. Алгоритм

1. Считываем n и m.
2. Считываем имена кандидатов:
   • сохраняем их в массив names;
   • строим словарь имя -> номер.
3. Считываем n бюллетеней:
   • каждое имя заменяем на его номер;
   • сохраняем бюллетень как список длины m.
4. Заводим массив eliminated, где отмечаем, выбыл ли кандидат.
5. Храним число оставшихся кандидатов alive.

Дальше запускаем цикл по раундам:

1. Создаём массив votes из m нулей.
2. Для каждого бюллетеня:
   • идём по кандидатам в порядке предпочтения;
   • первый невыбывший кандидат получает голос.
3. Проверяем, есть ли среди невыбывших кандидат, для которого votes[i] * 2 > n.
   • Если есть, выводим его имя и завершаем программу.
4. Если alive == 1, выводим имя единственного невывшего кандидата и завершаем программу.
5. Иначе ищем кандидата на выбывание:
   • только среди невыбывших;
   • минимальное число голосов;
   • при равенстве — максимальное по лексикографическому порядку имя.
6. Помечаем найденного кандидата как выбывшего и уменьшаем alive.

4. Почему это работает

Докажем, что алгоритм точно воспроизводит правила из условия.

1. Подсчёт голосов в раунде выполняется правильно

Для каждого бюллетеня алгоритм перебирает кандидатов в том порядке, в котором они указаны в бюллетене, и находит первого кандидата, который ещё не выбыл.

По условию именно этот кандидат и должен получить голос в текущем раунде. Значит, массив votes после обработки всех бюллетеней содержит правильные результаты раунда.

2. Победитель по большинству определяется правильно

После подсчёта голосов алгоритм проверяет для каждого невыбывшего кандидата условие votes[i] * 2 > n.

Это в точности эквивалентно условию «кандидат набрал строго больше половины от общего числа бюллетеней». Если такой кандидат найден, алгоритм сразу выводит его, как и требует условие.

3. Случай с одним оставшимся кандидатом обрабатывается правильно

Если после очередных выбываний остался ровно один кандидат, условие задачи объявляет его победителем.

Алгоритм хранит число оставшихся кандидатов в переменной alive и при alive == 1 действительно выводит единственного невывшего кандидата.

4. Кандидат на выбывание выбирается правильно

Алгоритм просматривает всех невыбывших кандидатов и выбирает:

• сначала того, у кого минимальное число голосов;
• при равенстве — того, чьё имя лексикографически больше.

Это полностью совпадает с правилом выбывания из условия.

5. Алгоритм завершится

В каждом раунде, если победитель не найден и кандидат не единственный, алгоритм выбрасывает ровно одного кандидата.

Число кандидатов конечно, значит процесс не может идти бесконечно. Рано или поздно либо кто-то наберёт большинство, либо останется один кандидат.

Следовательно, алгоритм всегда завершится и выдаст правильного победителя.

5. Сложность

Пусть:

• n — число бюллетеней,
• m — число кандидатов.

В одном раунде:

• для каждого из n бюллетеней в худшем случае просматриваются все m кандидатов;
• ещё O(m) уходит на проверку победителя и поиск кандидата на выбывание.

Итого один раунд работает за O(n * m).

Раундов не больше m, потому что каждый раз выбывает один кандидат.

Общая сложность:

• O(n * m * m)

При m <= 20 это более чем достаточно.

Память:

• хранение всех бюллетеней занимает O(n * m).

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> names(m);
    unordered_map<string, int> id;
    for (int i = 0; i < m; i++) {
        cin >> names[i];
        id[names[i]] = i;
    }

    vector<vector<int>> ballots(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            string s;
            cin >> s;
            ballots[i][j] = id[s];
        }
    }

    vector<bool> eliminated(m, false);
    int alive = m;

    while (true) {
        vector<int> votes(m, 0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int c = ballots[i][j];
                if (!eliminated[c]) {
                    votes[c]++;
                    break;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            if (!eliminated[i] && votes[i] * 2 > n) {
                cout << names[i] << "\n";
                return 0;
            }
        }

        if (alive == 1) {
            for (int i = 0; i < m; i++) {
                if (!eliminated[i]) {
                    cout << names[i] << "\n";
                    return 0;
                }
            }
        }

        int minVotes = -1;
        int toEliminate = -1;
        for (int i = 0; i < m; i++) {
            if (eliminated[i]) continue;
            if (minVotes == -1 || votes[i] < minVotes ||
                (votes[i] == minVotes && names[i] > names[toEliminate])) {
                minVotes = votes[i];
                toEliminate = i;
            }
        }

        eliminated[toEliminate] = true;
        alive--;
    }

    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

names = []
id_by_name = {}
for i in range(m):
    name = input().strip()
    names.append(name)
    id_by_name[name] = i

ballots = []
for _ in range(n):
    parts = input().split()
    ballots.append([id_by_name[x] for x in parts])

eliminated = [False] * m
alive = m

while True:
    votes = [0] * m

    for ballot in ballots:
        for c in ballot:
            if not eliminated[c]:
                votes[c] += 1
                break

    for i in range(m):
        if not eliminated[i] and votes[i] * 2 > n:
            print(names[i])
            raise SystemExit

    if alive == 1:
        for i in range(m):
            if not eliminated[i]:
                print(names[i])
                raise SystemExit

    min_votes = None
    to_eliminate = -1
    for i in range(m):
        if eliminated[i]:
            continue
        if min_votes is None or votes[i] < min_votes or (votes[i] == min_votes and names[i] > names[to_eliminate]):
            min_votes = votes[i]
            to_eliminate = i

    eliminated[to_eliminate] = True
    alive -= 1