ICPC国内予選2016 B問題： 当選者を探せ！

問題. 当選者を探せ!

最も多くの票を獲得した候補者が次期委員長に選出される．選挙の開票を一票ずつ行っていくときに，当選者が確定するところと当選者を求めよ．もし，当選者が確定しない場合は"TIE"と表示せよ．

制約：

解法. シミュレーション

回目の開票で当選者が確定するときは，その時点での投票数2位の候補者が残り全部の票を獲得しても投票数が1位の候補者よりも少ないときである．したがって，各開票時での各候補者の獲得票数と票数が1番と2番の人を記憶しながらシミュレーションをすればよい．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    char c;

    while (cin >> n, n) {
        vector<int> cnt((int)('Z' - 'A') + 1);
        pair<int, int> idx(0, 1);
        int find = -1;

        for (int i = 0; i < n; ++i) {
            cin >> c;

            if (find != -1) continue;

            int cur = (int)(c - 'A');
            ++cnt[cur];
            if (cur != idx.first && cnt[idx.second] < cnt[cur]) idx.second = cur;
            if (cnt[idx.first] < cnt[idx.second]) swap(idx.first, idx.second);

            if (cnt[idx.second] + (n - i - 1) < cnt[idx.first]) find = i + 1;
        }

        if (cnt[idx.first] == cnt[idx.second]) cout << "TIE\n";
        else cout << (char)(idx.first + 'A') << " " << find << '\n';
    }

    return 0;
}

まとめ

TIEのとき委員長どうするんでしょうね．
想定解法[1]もだいたい同じ．

参考文献

[1] 審判長による国内予選講評（確定版） | ACM-ICPC 2016 Asia Tsukuba Regional