見出し画像

AtCoder Beginner Contest 205を振り返る D問題

D - Kth Excluded

問題

長さNのソート済みの整数列AとQ個のクエリが与えられます。クエリでは正整数Kが与えられるので、Aに含まれない正整数の内小さい方から数えてK番目の整数を求める問題

制約

1 <= N,Q<= 10^5
1 <= A1 <= A2 ... <= 10^18
1 <= K <= 10^18

所感

最初、与えられなかった列を出して回答しようと思ったんですが整数列Aの最大値が「10の18乗」で、ループ回すだけでTLE確定だったので止めました。これはバイナリーサーチなんじゃないかと思いつつも実装方法が全然わからなかったので回答できず、解説動画を見て以下の回答を作成しました。

解説動画みて作成したコード

import bisect
n, q = map(int, input().split())
a = list(map(int, input().split()))
c = [a[i] - i -1 for i in range(n)]

for _ in range(q):
   k = int(input())
   r = bisect.bisect_left(c, k)
   if r == 0: ans = k
   else:
       ans = a[r-1] + (k-c[r-1])
   print(ans)

Cを出すところまではわかるんですが、最終的な答えの部分がなかなか出てこなさそうです。今回は「bisect」を知っただけでも儲けものということで。


この記事が気に入ったらサポートをしてみませんか?