Atcoder Beginner Contest 161 B

2020年4月8日

Atcoder ABC 161 B

Atcoder ABC 161 Bの問題をPythonで解説していきます。
https://atcoder.jp/contests/abc161/tasks/abc161_b

B – Popular Vote


実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

N 種類の商品に対して人気投票を行いました。商品 i は Ai 票を得ています。

この中から人気商品 M 個を選びます。ただし、得票数が総投票数の 14M 未満であるような商品は選べません。

人気商品 M 個を選べるなら Yes、選べないなら No を出力してください。

制約

  • 1≤M≤N≤100
  • 1≤Ai≤1000
  • Ai は相異なる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A1 … AN

出力

人気商品 MM 個を選べるなら Yes、選べないなら No を出力せよ。

解説

N種類の商品の中から得票数が総投票数の1/4M以上であるようなものをM個以上選べるかといった問題です。
まずは票数 A をリストで受け取り,それを大きい順にソートしてやります。
そしてそのソートしてあげたもののうち,上位M個の値がすべて総投票数の1/4M以上であればよいわけです 。
リスト A は大きい順にソートしてあるわけですから,結局リスト A の上から M 番目のものが総投票数の1/4M以上であれば,必然的にリスト A の上位 M 個の値は総投票数の1/4M以上となります。
従って,実装すべきことは

  • リスト A を降順にソートする
  • A の M 番目の値が総投票数の1/4M以上であるか判定し,そうであれば “Yes" を,そうでなければ “No" を出力する

ということになります。

k,m = map(int, input().split())
a = list(map(int, input().split()))

# リスト a の総投票数を s に格納する
s = sum(a)

# リスト a を降順にソートする
a.sort(reverse=True)

# リスト a の上から m 番目を判定する
if a[m-1] >= s*(1/4/m):
    print('Yes')
else:
    print('No')

他の問題も解説しているので,ぜひ見ていってください!
ABC 161 A
ABC 161 C
ABC 161 D
ABC 161 E
ABC 161 F