基準点以上の受験者の人数

二分探索
問題 09
ふつう
目安 31 分

低い順に並んだ受験者の点数と、いくつもの基準点が与えられる。基準点ごとに全員を数え直さず、二分探索で人数を答える練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

社内の資格試験を N 人が受けました。N 人の点数が、低い順 (同じ点数の人がいれば続けて) に並べて与えられます。そのあと、合格の基準点の候補が Q 個与えられます。基準点の候補 x のそれぞれについて、「x 点以上を取った人は何人か」を 1 行ずつ出力してください。

入力の形式

N
a_1 a_2 ... a_N
Q
x_1
x_2
...
x_Q

1 行目に受験者の人数 N、2 行目に N 人の点数 a_i が半角の空白 1 つで区切られて並びます。3 行目に基準点の候補の数 Q、4 行目から Q 行は、1 行に 1 つの基準点 x_k です。

出力の形式

Q 行を出力します。k 行目に、x_k 点以上を取った人の数を書きます。1 人もいなければ 0 を書きます。

制約

N と Q は、どちらも 1 以上 200000 以下です
点数 a_i は、0 以上 1000000 以下の整数です
点数は低い順に並んでいます。a_1 は a_2 以下、a_2 は a_3 以下、と続き、a_(N-1) は a_N 以下です
基準点 x_k は、0 以上 1000000 以下の整数です

入力と出力の例

例 1

6 人の点数が 40、55、60、60、72、90 です。60 点以上は 60、60、72、90 の 4 人、91 点以上は 0 人、0 点以上は全員の 6 人、56 点以上は 60 点からなので 4 人です。

入力

6
40 55 60 60 72 90
4
60
91
0
56

出力

例 2

受験者が 1 人で、基準点がその人の点数とちょうど同じときと、1 点だけ上のときです。

入力

出力

1
0

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

点数の並びの中で、x 以上になる最初の位置 (0 から数える) を二分探索で求めます。その位置より後ろの人が全員 x 点以上なので、答えは N から位置を引いた数です。x がどの点数より大きいときは位置が N になり、答えは 0 です。1 つの基準点に O(log N) なので、全部で O(N + Q log N) です。

Python

import sys
from bisect import bisect_left

data = sys.stdin.read().split()
n = int(data[0])
scores = list(map(int, data[1:1 + n]))
q = int(data[1 + n])
queries = list(map(int, data[2 + n:2 + n + q]))

answers = [n - bisect_left(scores, x) for x in queries]
print("\n".join(map(str, answers)))

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const scores = data.slice(1, 1 + n);
const q = data[1 + n];
const queries = data.slice(2 + n, 2 + n + q);

// x 以上になる最初の位置。どの点数も x より小さければ n
function lowerBound(x) {
  let low = 0;
  let high = n;
  while (low < high) {
    const mid = (low + high) >> 1;
    if (scores[mid] < x) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return low;
}

const answers = queries.map((x) => n - lowerBound(x));
console.log(answers.join("\n"));

計算量

時間は O(N + Q log N) です。log N は 20 万でも 18 ほどなので、基準点 20 万個でも 400 万回ほどの比べで済みます。基準点のたびに全員を見て数える書き方は O(N × Q) で、N と Q が 20 万の入力では 400 億回になり、時間切れになります。Python の sum(1 for a in scores if a >= x) のように 1 行で書いても、中では全員を見ているので同じです。

よくある間違い

「x より大きい」と「x 以上」を取り違える。x 点ちょうどの人も数えるので、x 以上になる最初の位置を探します。Python では bisect_right ではなく bisect_left です
同じ点数の人が何人も並ぶときに、見つけた 1 人の位置をそのまま使ってしまう。二分探索は「x 以上になる最初の位置」を探すように書きます
x がどの点数より大きいときの答えを 0 にし忘れる。探す範囲の右端を N - 1 ではなく N にしておくと、位置が N になって自然に 0 が出ます
答えを 1 つずつ print して出力が遅くなる。Q が 20 万行なら、まとめて 1 回で出力するほうが速く書けます

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n = int(data[0])
scores = list(map(int, data[1:1 + n]))
q = int(data[1 + n])
queries = list(map(int, data[2 + n:2 + n + q]))

# ここから書く

入力

6
40 55 60 60 72 90
4
60
91
0
56

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します