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

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

JOI 春合宿 2011 day4-3 IOI (難易度 6)

JOI JOI春合宿 JOI難易度6 AtCoder 二分探索 二分探索:lower_bound 各kに対して 算数と数学 最大値と最小値を求める 現実世界の題材を扱った問題 テーマにストーリー性のある面白い問題

lower_bound を上手に駆使する系

問題概要

K 人の選手が、コンテストに参加している。各選手の現在の得点は P_{1}, \dots, P_{K} である。

どの選手についても、今後加算される可能性のある得点は、 0 点以上 100(N-M) 点以下となっている ( N 問中 M 問の競技が終了しているという設定)。

競技終了時において、「 x 点以上を獲得している選手の人数が K/12 以上である」という条件を満たす最大の x を A として、 A 点以上を獲得した選手に金メダルが贈られる。

各選手に対して、

  • その選手が金メダルを獲得できることが確実かどうか
  • そうでない場合に、金メダルを獲得できる可能性があるかどうか

を判定せよ。

制約

  • 1 \le K \le 10^{5}
  • 1 \le M \le N \le 10^{7}

考えたこと

V = 100(N-M) (追加得点の最大値)、 L = (K+11)/12 - 1 (金メダル獲得者より得点が高い人の人数の上限値) とする。

まず、金メダル確実であるとは、

  • 自分の追加得点は 0 点
  • 自分以外の追加得点は全員が V 点

という状況であっても金メダルが獲れることを言う。これは言い換えると

P_{1}, \dots, P_{K} のうち、 P_{i} - V よりも大きい値となるものが、 P_{i} を除いて L 個以下である

となる。 P_{1}, \dots, P_{K} のうち、 P_{i} - V よりも大きい値となるものの個数は、 P をソートした配列上で二分探索 (upper_bound() など) を用いることで O(\log K) で計算できる。

次に金メダルの可能性があるとは

  • 自分の追加得点が V 点
  • 自分以外の追加得点は全員が 0 点

という状況であれば金メダルが獲れることを言う。これは言い換えると

P_{1}, \dots, P_{K} のうち、 P_{i} + V よりも大きい値となるものが、 L 個以下である

となる。これも同様に、 O(\log K) で計算できる。

コード

全体として計算量は O(K \log K) となる。

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

int main() {
    int K, N, M;
    cin >> K >> N >> M;
    int V = 100*(N-M), L = (K+11)/12-1;
    vector<int> P(K);
    for (int i = 0; i < K; ++i) cin >> P[i];
    auto Q = P;
    sort(Q.begin(), Q.end());

    // x 点より多く獲得した人が何人いるか
    // ただし y > x の場合は 1 を引く
    auto calc = [&](int x, int y) -> int {
        int it = upper_bound(Q.begin(), Q.end(), x) - Q.begin();
        return (y > x ? K - it - 1 : K - it);
    };

    vector<int> res(K, 0);
    for (int i = 0; i < K; ++i) {
        if (calc(P[i]-V, P[i]) <= L) res[i] = 2;
        else if (calc(P[i]+V, P[i]) <= L) res[i] = 1;
    }
    for (int i = 0; i < K; ++i) if (res[i] == 2) cout << i+1 << endl;
    cout << "--------" << endl;
    for (int i = 0; i < K; ++i) if (res[i] >= 1) cout << i+1 << endl;
}