模擬国内2017C: クイズ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2825

問題

参加者人、問題数問のクイズ大会を考える。また、問目の問題の得点はである。
このクイズ大会では、問目に正解する可能性がある参加者が人おり、それぞれであることがわかっている。
この設定で、問目の得点をその時点でどのような得点状況でも正解すれば逆転できるように設定する。
そのような得点の最小値を出力する。

解法

それぞれの人に対して、その人が取り得る得点の最小値と最大値を計算しておく。
そのような配列を, として、あわせて誰の得点なのかも保持しておく。
計算方法としては、

• 最小 → 出来るだけ正解しない、候補が自分1人のときはしょうがないので正解する。
• 最大 → 出来るだけ正解する。

を愚直にやれば良い。

最後にとすれば答えが出るのだが、最大値と最小値の保持者が同じときに注意が必要であり、 このとき、 のようにする必要がある。

コード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4896138#1

int n, m;

void solve() {
    using P = pair<int, int>;

    vector<P> ma(n), mi(n);
    for (int i = 0; i < m; i++) {
        int s, k;
        cin >> s >> k;
        for (int j = 0; j < k; j++) {
            int id; cin >> id;
            if (k == 1) mi[id-1].first += s;
            ma[id-1].first += s;
        }
    }

    for (int i = 0; i < n; i++) {
        ma[i].second = i;
        mi[i].second = i;
    }

    sort(ma.rbegin(), ma.rend());
    sort(mi.begin(), mi.end());

    int ans = ma[0].first - mi[0].first;
    if (ma[0].second == mi[0].second) {
        //ここはmaxです(戒め)
        ans = max(ma[0].first - mi[1].first, ma[1].first - mi[0].first);
    }

    cout << ans + 1 << endl;
}