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

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

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

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

問題概要

制約

考えたこと

コード