JOI難易度６ 国際情報オリンピック

問題原文

https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day4.pdf

問題要旨

人の選手からなる競プロの大会を考える。
大会では0点から100点までの点を取得できる問題が 問あり、 問が終了した時点での各選手の得点は 点である。
また金メダルを取れる条件を以下のように定める。

• を 問の合計点数が 点以上の選手の人数が全体の 以上となるような最大の数とするとき、実際に 点以上獲得する

確実に 問終了時点で、確実に金メダルが取れる選手と、金メダルが取れる可能性がある選手を求めよ。

• 
• 

解法

確実に金メダルが取れる、とは「このあと自分が全部０点で、他の選手が全部満点であっても、自分が上位 に入れる」ことであり、
金メダルが取れる可能性がある、とは「このあと自分が全部１００点で、他の選手が全部０点の時、、自分が上位 に入れる」ことである。

これは各選手について、「このあと全部０点だった場合の結果」と「このあと全部満点だった場合の結果」を計算の上ソートしておいて、にぶたんするとで判定できる。

ただし、最初から 以上に入っている選手については、判定の際に自分と競い合うことになってしまうので、その分判定のindexを１緩めてやる。

実装

import sys
from math import ceil
from bisect import bisect_right

my_input = sys.stdin.readline
K, N, M = map(int, input().split())
threshold_index = (K - (ceil(K / 12)))

P = [int(my_input()) for _ in range(K)]
P_min = sorted([(p, i) for i, p in enumerate(P, start=1)])
remain_max = (N - M) * 100
P_max = sorted((p + remain_max, i) for i, p in enumerate(P, start=1))

C = set([i for p, i in P_min[threshold_index:]])

ans1 = []
for (p, i) in P_min:
    r = bisect_right(P_max, (p, float('inf')))
    if i in C:
        r += 1
    if r > threshold_index:
        ans1.append(i)

ans2 = []
for (p, i) in P_max:
    r = bisect_right(P_min, (p, float('inf')))
    if i in C:
        r += 1
    if r > threshold_index:
        ans2.append(i)

ans = sorted(ans1) + ['--------'] + sorted(ans2)
print(*ans, sep="\n")

感想

たいちょうわるい〜〜〜、、、、、、、めっちゃじかんかかってしまった。。。。