日刊競プロ ABC 236 -C - Route Map-
問題文
AtCoder 鉄道のとある路線には N 個の駅が存在し、始点から終点に向かって i(1≤i≤N) 番目の駅の名前は Siです。普通列車は全ての駅に止まりますが、急行列車は全ての駅に止まるとは限りません。具体的には、急行列車は M(M≤N) 個の駅にのみ止まり、j(1≤j≤M) 番目に止まる駅の名前は Tjです。
ただし、T1=S1かつ TM=SN、すなわち急行列車は始点と終点の両方に止まることが保証されます。N 個の駅それぞれについて、その駅に急行列車が止まるかどうか判定してください。
制約
2≤M≤N≤10**5
N,M は整数
Si(1≤i≤N) は英小文字のみからなる 1 文字以上 10 文字以下の文字列
Si≠Sj(i≠j)
T1=S1かつ TM=SN(T1,…,TM) は (S1,…,SN) から 0 個以上の文字列を選んで取り除き、残った文字列を元の順序で並べることで得られる
考えたこと
Tの要素にSの要素が含まれていればYes，そうでなければNoとなる．Nが最大で10**5，Mも10**5なので，全探索していると間に合わないと考えた．そこで二分探索を使って計算量を減らそうと考えた（logN×Mまで減らせると考えた）
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
N,M = map(int,input().split())
Slist = list(map(str,input().split()))
Tlist = list(map(str,input().split()))
ans =[]
d ={}
for i in range(N):
d[Slist[i]]=i
ans.append(i)
search=[]
for j in range(M):
search.append(d[Tlist[j]])
for i in range(N):
if binary_search(search, ans[i] ,len(search))!=-1:
print ("Yes")
else:
print ("No")
最初に文字列を数字に変換できる辞書を用意し，SとTを数列に変換している．そのあとSに対してTで2分探索し，見つかればYes,見つからなければNoとした．
公式解説
SにTが含まれているかをチェックすれば良いので以下で良いとのこと．．．
n, m = map(int, input().split())
s = input().split()
t = set(input().split())
for x in s:
print("Yes" if x in t else "No")