初中級者が解くべき過去問精選 100 問茶コーダーが解いてみた #5 ( 二分探索編 )

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？
過去の記事についてはこちら！！
- 全探索シリーズ
全探索：二分探索
最後に

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今回は第５回目の二分探索！！

過去の記事についてはこちら！！

全探索シリーズ

全探索：二分探索

全探索：二分探索の分野は全部で６問あるので、紹介したいと思います！

18. Binary Search

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

これは正直どこで二分探索を使用するのかわかりませんでした。
なので、s, tの両方に含まれている集合を論理積で取ってあげてその長さを出力することでAC出来ました。
setにすれば&をとることが可能です。

n = int(input())
s = set(map(int,input().split()))
q = int(input())
t = set(map(int,input().split()))
print(len(s&t))

19. B - ピザ

https://atcoder.jp/contests/joi2009ho/tasks/joi2009ho_b

これは苦労しました。まず問題文を読むのに苦労しました。
長くて読む気がしばらくありませんでした...

解法としては、店は円形になっているので、まず１直線状に変換します。
その際、本店の座標は0, dの２つになります！

その後、店を昇順に並べてリストでの二分探索を用います。
それで家から一番近い店の左右での距離を比較して、小さい方を足し合わせていくことでAC出来ます。

from bisect import bisect_right
d = int(input()) # 全長
n = int(input()) # 店舗の個数
m = int(input()) # 注文の個数
shop = [0]
home = []
ans = 0
for i in range(n-1):
    shop.append(int(input()))
for i in range(m):
    home.append(int(input()))
shop.append(d) # 本店は１直線上では0とdは同値
shop.sort()

for i in home:
    x = bisect_right(shop, i)
    ans += min(abs(shop[x-1] - i), abs(shop[x] - i))
print(ans)

20. C - Snuke Festival

https://atcoder.jp/contests/abc077/tasks/arc084_a

これはやりやすい問題でした。
方針としては、全てを探索してしまうとTLEしてしまうので、Bの配列を基準にAはそれよりも小さい値、Cはそれよりも大きい値の数をbisect_left, bisect_rightで調べて掛け合わせたものを足すことでAC出来ました！！

from bisect import bisect_left
from bisect import bisect_right
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect_left(a, b[i])
    y = bisect_right(c, b[i])
    ans += x * (n - y)
print(ans)

21. D - 射撃王

https://atcoder.jp/contests/abc023/tasks/abc023_d

これは個人的には今までの中で最難関問題でした。流石に青Diffなだけはあります。

方針としては、ある決めた時間内に風船を割らないといけないと仮定し、その値を二分探索で絞っていきます。
二分探索のコードはめぐる式二分探索を使用しました。

ポイントはその決めた値をxとすると、(x - h[i])//s[i]以内に絞らなければいけないことがわかります。あとは順番に割っていけるかを鑑定してAC出来ました。

要復習問題です...

n = int(input())
h = [0]*n
s = [0]*n
for i in range(n):
    h[i], s[i] = map(int,input().split())

def is_ok(x):
    l = []
    for i in range(n):
        l.append((x - h[i])//s[i]) # この時間までに割らなきゃいけない
    l.sort() # 小さいものから割る
    for j in range(n):
        if (l[j] < j):
            return False # アウトー
    return True

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

print(meguru_bisect(0, 10**18))

22. B - ムーアの法則

https://atcoder.jp/contests/arc054/tasks/arc054_b

これは面白かった！
方針が全く立たずに解法を調べてみたら三分探索を使用すると書かれていました！
三分探索なんて言葉は聞いたことなかったので衝撃を受けました...

こちらのサイトでイメージできました！
qiita.com

三分探索でmid_leftとmid_rightのの最大値の方をどんどん小さく更新していきます！
そうすることで差がとても小さくなるまで探索していくことで最小値を求めることが出来ました！

# 三分探索
p = float(input())
def f(x):
    return x + p/2**(x/1.5)

ma = 1000
mi = 0
while ma - mi > 0.000000001:
    mid_left = (ma - mi)/3 + mi
    mid_right = (ma - mi)*2/3 + mi
    if f(mid_left) >= f(mid_right): # 0 ~ mid_leftには最小値が存在しない
        mi  = mid_left
    else: # mid_right ~ maには最小値が存在しない
        ma = mid_right
print(f(ma))

23. C - ダーツ

https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c

今回ラストの問題です！
４本ダーツを放ちますが、全探索してはTLEしてしまします。
そこで用いるのが半分全列挙というアルゴリズムです！！
ちょうど先週のABC184のF問題で半分全列挙というのが出題されてACしたので問題文とコードを載せておきます！

半分全列挙の例題 : ABC184_F. Programming Contest (1423diff)

atcoder.jp

この問題ではN <= 40なのでbit全探索をしてはTLEです。
なので前半の20個と後半の20個を分けてあげて組み合わせることでAC出来ます！！

ABC184_FをACしたコード

from bisect import bisect_right
from itertools import product
n,t = map(int,input().split())
a = list(map(int,input().split()))
left = [0]
right = [0]
ans = 0

for i in product([0,1], repeat = min(20, n)):
    cnt = 0
    for j in range(min(20, n)):
        if i[j] == 1:
            cnt += a[j]
    left.append(cnt)
left = list(set(left))
left.sort()

for i in product([0,1], repeat = max(0, n - 20)):
    cnt = 0
    for j in range(max(0, n - 20)):
        if i[j] == 1:
            cnt += a[j + 20]
    right.append(cnt)
right = list(set(right))
right.sort()

for i in range(len(left)):
    if left[i] > t: continue
    j = right[bisect_right(right, t - left[i]) - 1]
    ans = max(ans, left[i] + j)
print(ans)

このように全列挙でTLEしてしまうものは半分ずつに分けることでACすることが出来ます。
ダーツの方針としては、まず２本打って獲得できる点数を全列挙します。これはTLEしません。
そのあとで、そのリストの値をそれぞれ調べて残りの２本で獲得できる最大の値を bisect_left で探索して最大値を取っていくことでAC出来ます！！

ほとんど何も見なくても書けるようにはなりましたが、少し不安があるので定期的に復習して行きたいです！！

# 半分全列挙
from bisect import bisect_left
n,m = map(int,input().split())
a = [0]*n
for i in range(n):
    a[i] = int(input())
a.append(0)
num = []
for i in range(n):
    for j in range(i,n+1):
        num.append(a[i] + a[j])
num.sort()

ans = 0
for i in range(len(num)):
    if num[i] < m:
        ans = max(ans, num[i])
    x = m - num[i] 
    if x > 0: # 更に２本打っちゃうよーーー
        y = bisect_left(num, x)
        #print(i,y,x,ans)
        if y > 0 and num[i] + num[y-1] <= m: # 0だと追加する必要ないしバグるね
            ans = max(ans, num[i] + num[y-1])
print(ans)

最後に

二分探索でさえつまずいていたのに、最後の方には三分探索なんて言葉も出てきてかなり苦戦しましたが、全部が新しい知見でとても勉強になって良かったです！

次はいよいよDFS, BFSです。いよいよなんもわからんですが、頑張っていきたいと思います。

それではまた #6 でお会いしましょう！！