Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Contest

Category: JOI Tag: greedy

Contest

問題概要


nカ国それぞれ2人の選手の成績がある.
いま成績がどの国の成績なのか一部分からなくなってしまった.
国cの順位として考えられる最高の順位は何位か.

解法


まず国cの成績は高い方がいいので不明なのがあるならできるだけ高いのを割り当てる.
あとは決まっていない国はgreedyにcの得点以下で最大の得点になるように組を作っていけば良い.
始めは片方だけ分かっている国に対して所属不明な点数を, そのあとに所属不明な点数同士を組み合わせる.
出来ない場合は国が不明な得点のうち最大のものを使う.

greedyでよい理由
点差が関係ないというのがポイント
国cの点数をbとする
ある国の片方の点数が決まっているとき, b以下になる所属不明な点数が存在するとする.
今そのような点数のうち最大のものxを使うとする
xを使わずにとっておいて, その国をbより上の点数にして他の国の点数をb以下にした場合と, 使ってこの国の点数ををb以下にして他の国の点数をbより大きくするのでは違いはない(bより大きくする場合は使われていない所属不明な点数のうち最大のものを使っていくこと).
またxで点数をb以下に出来る場合, それ未満の数でもb以下にできるのでxを使うべき.
不明なもの同士を組み合わせる場合も, 1つを固定して考えれば同じように考えることができる.

コード


(Contest.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

int n, c, sc[4096], cnt[4096];
vector<int> s[3];

int solve()
{

        for (int i = 0; i < n; i++) if(cnt[i] and i != c) s[cnt[i]].push_back(sc[i]);
        for (int i = 0; i < 3; i++) sort(begin(s[i]),end(s[i]));
        while(cnt[c] < 2) {
                sc[c] += s[0].back();
                cnt[c]++;
                s[0].pop_back();
        }

        int ans = n, b = sc[c];
        for(auto &e: s[2]) if(b >= e) ans--;
        for(auto &e: s[1]) {
                int d = b-e;
                auto it = upper_bound(begin(s[0]),end(s[0]),d);
                if(it == begin(s[0])) {
                        s[0].pop_back();
                        continue;
                }
                it--;
                s[0].erase(it);
                ans--;
        }

        for (auto it = begin(s[0]); it != end(s[0])-1; it++) {
                if(s[0].size() < 2) break;
                int d = b-*it;
                auto jt = upper_bound(it+1,end(s[0]),d);
                jt--;
                if(it==jt) {
                        s[0].pop_back();
                        continue;
                }
                s[0].erase(jt);
                ans--;
        }
        return ans;
}

void input()
{
        cin >> n >> c;
        c--;
        for (int i = 0; i < 2*n; i++) {
                int a, b; cin >> a >> b;
                if(b) sc[b-1] += a, cnt[b-1]++;
                else s[0].push_back(a);
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments