C - Counting 2

皆さん、こんにちは！

ハリーです。今回はパナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) に出題された C - Counting 2 を解いていきたいと思います。私はコンテスト中にこの問題を解くことができなかったので、しっかりと復習していきたいと思います。それでは、解いていきましょう！

C - Counting 2

問題文

$N$ 人の生徒からなるクラスがあり、$i(1 \leq i \leq N)$ 番目の生徒の身長は $A_i$ です。

$j=1,2,…,Q$ について、以下の質問に答えてください。

制約

• $1 \leq N, Q \leq 2 × 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq x_j \leq 10^9$
• 入力は全て整数

入力例１

3 1
100 160 130
120

出力例１

2

入力例２

5 5
1 2 3 4 5
6
5
4
3
2

出力例２

0
1
2
3
4

入力例３

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

出力例３

5
3
5
5
5

実装方法

bisect のモジュールをインポ―トします。

from bisect import bisect_left

入力を受け取り、A の配列を昇順にソートします。

N, Q = map(int, input().split())

A = list(map(int, input().split()))

A.sort()

for 文内で入力 $x$ の値を受け取り、bisect_left で昇順にソートされた配列 A の x 以下の人数を取りだし、全体の人数から x 以下の人数を引いた値を出力します。

for i in range(Q):

  x = int(input())

  print(N - bisect_left(A, x))

ACコード

from bisect import bisect_left

N, Q = map(int, input().split())

A = list(map(int, input().split()))

A.sort()

for i in range(Q):

  x = int(input())

  print(N - bisect_left(A, x))

おわりに

いかがだったでしょうか？今回の復習で bisect の理解を深めることができたので、良かったです。次も、また別なカテゴリの問題を解いていきたいと思います！

それでは皆さん、また来週！