AtCoder Beginner Contest 003 C – AtCoderプログラミング講座 をPython3で解く

Share

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

出典:
AtCoder Beginner Contest 003 C – AtCoderプログラミング講座

どういう順番で動画を観るかを、ある程度考察する必要がある問題。もっとも、この問題に関しては、直感でえいやっとやってもなんとかなる感じではある。

# AtCoder Beginner Contest 003 C - AtCoderプログラミング講座
# https://atcoder.jp/contests/abc003/tasks/abc003_3
# tag: 最大値 考察 高橋君

# まず、動画のうちレートの高い上位 K 個を選ぶほうがいいのは自明。

# あとはどのような順序で見るほうがいいのか、という問題になる。
# 直感的には、下から観る方が良さそうだけど……。

# ここで、仮に今のレートを R とし、レートが A, B の動画を
# 続けて観るとしてみる。

# すると最終的なレートは、
# R → (R + A) / 2 → (R + A + 2*B) / 4 となる
# つまり、あとから見る動画のほうが、最終的なレートに対する
# 寄与は大きくなる。
# というわけで、レートの低い順に動画を観ていく方針で良い。

def main():
N, K = map(int, input().split())
movies = list(map(int, input().split()))

movies.sort()

rating = 0

# ソートしたものの、上位 K 個を下から確認
for r in movies[N-K:]:
rating = (rating + r) / 2

print(rating)

main()

Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です