けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 187 D - Choose Me (茶色, 400 点)

ペア (A+B,A) の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった

問題概要

青木君と高橋君が選挙を行う。N 個の町があり、i 番目の町では

  • 青木派が Ai 人いる
  • 高橋派が Bi 人いる

ということがわかっている。高橋君はいくつかの町で選挙活動を行う。

  • 高橋君が選挙活動を行わない町では、青木君が Ai 票を獲得し、高橋君が 0 票を獲得する (高橋派は怠惰)
  • 高橋君が選挙活動を行う町では、青木君が 0 票を獲得し、高橋君が Ai+Bi 票を獲得する (青木派は裏切り者)

高橋君が青木君よりも多く票を獲得するようにしたい。高橋君が選挙活動を行うべき町の個数の最小値を求めよ。

制約

  • 1N2×105

考えたこと

高橋君は演説をしないと、まったく票をもらえないのねw

まず題意を把握するのに時間がかかった。こういう風に N 個の対象物 (今回は町) それぞれに対して、二つの「属性」(今回は青木派人数と高橋派人数) が与えられるような問題は、独特の思考を要することが多い。たとえば今回でいえば

  • 高橋君の得票数を増やしたいので Ai+Bi が大きいところを優先的に選挙したい
  • 青木君の得票数を減らしたいので Ai が大きいところを優先的に選挙したい

という 2 つの価値観があるのだ。このように、二つの「属性」が登場する問題では、相異なる 2 つの価値観に基づく順序付けが登場して、そのジレンマに悩まされることが多い。

嘘解法:ペア (A+B,A) でソート

上のようなジレンマから、次のような解法を考えた方が多かったようだ。


A+B が大きい順に選挙活動する、ただし A+B が等しい町同士では A が大きい順に選挙活動する


つまり、ペア (A+B,A) をキー (辞書順比較) として大きい順にソートするということだ。しかしこれは嘘だ。たとえば

  • (A,B)=(10,90),(20,79),(81,17)

を考えてみよう。上記の価値観に沿うと、(10,90),(20,79),(81,17) の順に演説に行きたくなる (総和が 100, 99, 98)。このとき

  • (10,90) の町に行っただけでは「高橋君: 100、青木君: 101」となってダメ

でも実際には

  • (20,79) の町に 1 個行くだけで、「高橋君: 99、青木君: 91」となるので OK

となっている。

正しくは

まず高橋君がどこにも演説に行かない場合を考えてみよう。このとき、Ai の総和を S として、

「高橋君: 0、青木君: S

となる。このとき、(Ai,Bi) で表される町へいくと

「高橋君: Ai+Bi、青木君: SAi

となる。このとき、青木君と高橋君との差がどのくらい縮まったのかに着目しよう。

  • 高橋君の票数は Ai+Bi だけ増えた
  • 青木君の票数は Ai だけ減った

ということで、差に着目すると

(Ai+Bi)(Ai)=2Ai+Bi

だけ縮まることになるのだ (before の状態に依らない)。つまり、


  • 最初の「差」は S である
  • i で選挙すると、「差」は 2Ai+Bi だけ減少する

ということがわかった。ここまで来ると簡単だ。2Ai+Bi が大きい方から順に選挙へ行けばよいのだ!!!

このように、2 つの属性値を扱う問題では、「差」に着目するとよいことがあったりする!!

コード

2Ai+Bi が大きい順にソートするので、計算量は O(NlogN) となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

    // ソート
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return A[i]*2+B[i] > A[j]*2+B[j];
        });

    // 2A[i] + B[i] が大きい順に「差」を減らしていく
    long long diff = 0;
    for (int i = 0; i < N; ++i) diff += A[i];
    int res = 0;
    for (auto i: ids) {
        ++res;
        diff -= A[i]*2 + B[i];
        if (diff < 0) break;
    }
    cout << res << endl;
}