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

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

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

AtCoder AtCoder400点 ABC-D 茶色diff 二値パラメータ問題 探索順序を工夫して解く ソート Greedy 変数変換して扱いやすい同型な問題を見出す 最小回数・最小個数を求める 非自明な比較関数でソートする 【問題集】ソート ソート:比較関数を設計する Greedy:条件を満たすまで大きい順に取っていく 最適化問題 最小コスト

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

問題概要

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

  • 青木派が A_{i} 人いる
  • 高橋派が B_{i} 人いる

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

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

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

制約

  • 1 \le N \le 2 \times 10^{5}

考えたこと

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

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

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

という 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

となっている。

正しくは

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

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

となる。このとき、 (A_{i}, B_{i}) で表される町へいくと

「高橋君: A_{i} + B_{i}、青木君: S - A_{i}」

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

  • 高橋君の票数は A_{i} + B_{i} だけ増えた
  • 青木君の票数は A_{i} だけ減った

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

(A_{i} + B_{i}) - (- A_{i}) = 2 A_{i} + B_{i}

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

  • 最初の「差」は S である
  • 町 i で選挙すると、「差」は 2 A_{i} + B_{i} だけ減少する

ということがわかった。ここまで来ると簡単だ。 2 A_{i} + B_{i} が大きい方から順に選挙へ行けばよいのだ！！！

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

コード

2 A_{i} + B_{i} が大きい順にソートするので、計算量は O(N \log N) となる。

#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;
}