CODE FESTIVAL 2015 あさぷろ Middle A – ヘイホーくんと最終試験をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
CODE FESTIVAL 2015 あさぷろ Middle A – ヘイホーくんと最終試験

この問題に限った話ではないが、小数をなるべく使わないようにするほうがいい。小数点誤差でやられることがしばしばある。
今回の問題でいうと、上記K個の平均点がR以上という条件だが、上位K個の点数の合計がK*R以上、と読み替えてやると、トラブルが起きにくい。
……まあ、実際にはこの問題ではよほど変な計算をしなければ誤差でやられることにはならないと思われるが、後日のために習慣づけておくようにしたい。

# CODE FESTIVAL 2015 あさぷろ Middle A - ヘイホーくんと最終試験
# https://atcoder.jp/contests/code-festival-2015-morning-middle/tasks/cf_2015_morning_easy_c
# tag: 平均値 ヘイホー君

# この問題に限らず、基本的な方針として、なるべく小数を
# 使用しないようにしたい。
# 書き方によっては、K==N のとき微妙に処理が変わるので注意すること。

def main():
    N, K, M, R = map(int, input().split())
    scores = [int(input()) for _ in range(N-1)]

    # コーナーケース (K==N) 対応のため、とりあえず 0 点を追加してから
    # ソートしておく。
    # もちろん、あとから個別に条件分岐させてもOK。
    scores.append(0)
    scores.sort(reverse=True)

    # 上位 K 個の平均が R 以上である必要がある。
    # つまり、上位 K 個の合計が、 R * K である必要がある。
    needed = K * R

    # 現在の上位 K 個の合計
    sum_now = sum(scores[:K])

    # すでに上回っているなら、0 点でもよい
    if sum_now >= needed:
        print(0)
        return
    
    # 上回っていない場合、少なくとも現在の上から K 個目の点数より
    # 高い点数を取る必要がある。
    # よって、上から K 個目の点数を差し引き、必要な点数を求める。
    # （先程のコーナーケース対応は、ここで必要）
    result = needed - (sum_now - scores[K-1])

    # 求めた点数が、満点を超えている場合は、達成不可能なので注意
    if result > M:
        print(-1)
    else:
        print(result)

main()

code_festival_2015_morning_middle_c.py view raw

関連

コメントを残すコメントをキャンセル