WBC004 A - 79 Good 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

あなたは東京大学の教員です。あなたが開講した科目では、 人の学生が受講し、学生 の成績は 点 でした。

しかし、東京大学には「優３割規定」というルールがあります。「優３割規定」とは、『 点以上の成績がつく学生の人数は受講者全体の 以下でなければならない』というルールです。このルールに違反すると、怒られが発生します。

怒られるのは嫌なので、あなたは「優３割規定」に違反しないように成績をつけ直すことにしました。あなたは任意の学生の点数を 点に変えることができます。最低で何人の学生の点数を 点に変えれば「優３割規定」をみたすことができるか求めてください。

制約

• 
• 
• 入力はすべて整数

解説

「あなた」の目的は、「優３割規定」を満たすこと──つまり、 点以上の人数を全体の 以下に抑えることです。

点以上の人数は、 の数字をforループなどで全部見て数えればよいです。

上限人数は、全体の人数の なので、 です。このままだと「 人」のように小数になってしまって扱いづらいので、小数点以下を切り捨てて としておくとよいでしょう。

こうして求めた結果が 点以上の人数上限人数 となっていたら、最初から「優３割規定」を満たしているので何もする必要はなく、答えは になります。

問題は 点以上の人数上限人数 のときです。「優３割規定」を守るためには、 点以上の人数 を何とかして減らさなければなりません。ここで、学生の点数を 点に変える能力の出番です。このアビリティをある学生に使ったとき何が起きるのか、学生の元の点数に着目して考えてみましょう。

• 点以下：何も起こらない
• 点以上： 点以上の人数が 人減る

よって、この問題は「点以上の学生を好きなだけ減らすことができる。何人減らせば上限人数以下になるか」という問題であることが分かりました。これは 点以上の人数上限人数 で計算できます。

実装例

解説通りの実装例

import math

def solve():
    # input
    n = int(input())
    a = list(map(int, input().split()))

    # 80点以上の人数
    yu_cnt = 0
    for score in a:
        if score >= 80:
            yu_cnt += 1

    # 上限人数
    yu_max = math.floor(0.3 * n)

    # 答えの計算
    if yu_cnt <= yu_max:
        ans = 0
    else:
        ans = yu_cnt - yu_max

    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

慣れた人向けの実装例

def solve():
    # input
    n = int(input())
    a = list(map(int, input().split()))

    yu_cnt = sum(x >= 80 for x in a)
    yu_max = n * 3 // 10

    ans = max(yu_cnt - yu_max, 0)

    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

ちなみに、math.floor(0.3 * n) でぞわぞわする方もいるかもしれませんが、今回の制約で誤差は出ません。

ひとこと

原案でした。時期的にもセンシティブな「優３割規定」というテーマで問題を作ってしまい非常に申し訳ないと思っています。