ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

過去問精選 100 問:二分探索編【Python解答例】

f:id:ebisuke33:20210322213151p:plain
今回もこちらの記事で紹介されている初中級者が解くべき過去問精選100 問を解いていきます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】 - Qiita

この記事は二分探索編です。

ALDS-4_B Binary Search

Binary Search

問題文

n 個の整数を含む数列 S と、q 個の異なる整数を含む数列 T を読み込み、T に含まれる整数の中で S に含まれるものの個数 C を出力するプログラムを作成してください。

解答例

n = int(input())
s = list(map(int,input().split()))
q =int(input())
t = list(map(int,input().split()))

c = 0

for i in range(q):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if s[mid] == t[i]:
            c += 1
            break
        elif s[mid] > t[i]:
            right = mid
        else:
            left = mid + 1

print(c)

解説

数列Sが昇順になっているので、二分探索でTの要素がSに含まれているか調べていきます。

二分探索では、まず数列Sの真ん中の要素を調べます。
数列Sの真ん中の要素とターゲットの値(この場合ではTの要素)を比較して、ターゲットの値が含まれていない半分の範囲を除外します。
次に残った範囲の真ん中の要素とターゲットの値を比較して…、という範囲を2分する作業を繰り返して探索する方法です。

上のプログラムはおそらく二分探索はできていますが、TLEとなってしまいました。

ACはできませんでしたが、二分探索の基本的な形だと思いますので記載しました。



ABC077 C - Snuke Festival

C - Snuke Festival

問題文

今年もすぬけ祭の季節がやってきました。りんごさんは、まず手始めにすぬけ君召喚の儀式を執り行おうと思っています。 儀式には祭壇が必要で、祭壇は上部、中部、下部の3つのカテゴリーのパーツ1つずつからなります。
祭壇の3カテゴリーのパーツがそれぞれN個ずつあります。i個目の上部のパーツのサイズはAi、i個目の中部のパーツのサイズはBi、i個目の下部のパーツのサイズはCiです。
祭壇を作るにあたっては、中部のパーツのサイズは上部のパーツのサイズより真に大きく、下部のパーツのサイズは中部のパーツのサイズより 真に大きくなければなりません。逆に、この条件を満たす任意の3つのピースを組み合わせて祭壇を作ることができます。
りんごさんが作ることのできる祭壇は何種類あるでしょうか。ただし、2つの祭壇が異なるとは、上部、中部、下部に使われるピースのうち 少なくとも1つが異なることを言います。

制約

・1≤N≤10^5
・1≤Ai≤10^9(1≤i≤N)
・1≤Bi≤10^9(1≤i≤N)
・1≤Ci≤10^9(1≤i≤N)
・入力は全て整数である

解答例

import bisect

n = int(input())

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

A.sort()
B.sort()
C.sort()

ans = 0

for i in range(n):
    target = B[i]
    a = bisect.bisect_left(A,target)
    c = bisect.bisect_right(C,target)
    ans += a * (len(C)-c)

print(ans)

解説

上・中・下部のパーツがあり、上にのるパーツは下のパーツより大きくないといけません。

中部のパーツを基準にして、上部の基準より小さいパーツの数と下部の基準より大きい数をaとcに代入します。

中部のパーツBiに対して作ることができる組み合わせはaとN-cをかけた値になるので、ループでBiを回してansを求めたらACでした。



2分探索のほかの問題も紹介されていましたが、とりあえず理解できたのはここまででした。

積み残しがどんどん増えていく…



初中級者が解くべき過去問精選100 問の記事をまとめたページはこちら
ebisuke33.hatenablog.com

蟻本の類題も解いていますので興味があればこちらもおすすめです。
ebisuke33.hatenablog.com