C. Students’ Revenge

問題

整数の組$(a_i, b_i)$が$n$個与えられる。 整数$p,k$($1 \le k \le p \le n)$が与えられる。 以下のようなゲームを行う。得点を辞書順で最大化するような選び方を答えよ。

  1. あなたは整数の組を$p$個適当に選ぶ。
  2. 相手はその中から以下の順で$k$個選ぶ。
    • $b$が小さい順に選ぶ。
    • $b$が同じであれば、$a$が小さい順に選ぶ。
  3. $(A,B)$が得点となる。ただし
    • $A$は手順2で選ばれた組の$a$の総和
    • $B$は手順2で選ばれなかった組の$b$の総和

解説

まず、$A$のみを最大化する方法を考える。 与えられた組を相手の選択の順にソートし、$p-k$番目以上に選ばれやすい組から、$a$が大きい順に$k$個選ぶ。 これに加え、相手に選ばれにくい順に組を$p-k$個選ぶ。 これにより$A$を最大化できる。

次に、$A$を固定したまま$B$を最大化する。 $a$が大きい順に$k$個選ぶところまでは同様にする。 残った組で、先程選んだ組のどれよりも選ばれにくいものに関して、これを$b$が大きいものから$p-k$個選ぶ。 これにより$(A,B)$を最大化でき、答えが求まる。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
struct order_t { int a, b; int i; };
bool eql(order_t x, order_t y) { return x.a == y.a and x.b == y.b; }
bool cmp_a(order_t x, order_t y) { return make_pair(x.b,-x.a) < make_pair(y.b,-y.a); }
bool cmp_b(order_t x, order_t y) { return make_pair(x.a,x.b) < make_pair(y.a,y.b); }
int main() {
    int n, p, k; cin >> n >> p >> k;
    vector<order_t> x(n);
    repeat (i,n) { cin >> x[i].a >> x[i].b; x[i].i = i; }
    sort(x.begin(), x.end(), &cmp_a);
    sort(x.begin() + (p-k), x.end(), &cmp_b);
    vector<order_t> ans;
    repeat (i,k) ans.push_back(x[n-i-1]);
    order_t it = *min_element(ans.begin(), ans.end(), &cmp_a);
    sort(x.begin(), x.begin() + (n-k), &cmp_a);
    for (int i = n-k-1; ans.size() != p; --i) {
        if (cmp_a(x[i],it) or eql(x[i], it)) ans.push_back(x[i]);
    }
    repeat (i,p) { if (i) cout << ' '; cout << ans[i].i+1; } cout << endl;
    return 0;
}