競プロ初中級者100問

ALDS1 4B 二分探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja

この問題は二分探索を用いて解くことができます。

方針

二分探索によりクエリの数値一つ一つが数列に含まれるかを判定していきます。

二分探索の計算量はO(logn)ですので、問題全体の計算量はO(qlogn)であり間に合います。

コード

1
2
3
4
5
6
7
8
9
10
11
12
import bisect
N = input()
INF = 10**10
S = list(map(int,input().split())) + [INF]
A = input()
T = list(map(int,input().split()))
ans = 0
for t in T:
    i = bisect.bisect_left(S, t)
    if (S[i] == t): # Sにtが含まれれば挿入点の値と等しい
        ans += 1
print(ans)

記事情報

  • 投稿日：2020年5月17日
  • 最終更新日：2020年5月17日