Atcoder水色への精選 100 問　二分探索(Python)

AtCoder Python 競プロ精進 精選100問 二分探索

水色になるための精選100問、前回から大分空いてしまいましたが引き続き更新していきます
今回は18~23までの「二分探索」です

qiita.com

前回↓
順列全探索
algo-archit.hatenablog.com

目次



18　ALDS_4_B - 二分探索

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B

pythonの二分探索ライブラリであるbisectを使います
bisect.bisect_right(もしくはbisect.bisect)で挿入したい数字をリストに入れたときの右端のインデックスを
bisect.bisect_leftで挿入したい数字をリストに入れたときの左端のインデックスを返してくれます

今回の問題ではこの両者の差が1以上の場合にカウントすることで解くことができます

pythonでの実装例

import bisect

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

point = 0

for i in t:
    if bisect.bisect_right(s,i)-bisect.bisect_left(s,i) > 0:
        point += 1
    
print(point)



19　JOI 2009 本選 2 - ピザ

問題文
https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4
ジャッジページ
atcoder.jp

店の配置を記録するリストの先頭と末尾に０とｄを追加してあげればOKです
右側と左側のそれぞれ最も近い位置の店のうち、距離が短い方を答えに足します

pythonでの実装例

import bisect

d = int(input())
n = int(input())
m = int(input())
# 店の座標（１番目の店だけ先頭と後方につける）
shop = [0]+[int(input()) for _ in range(n-1)] + [d]
shop.sort()
# 配送先
delivery = [int(input()) for _ in range(m)]

ans = 0

for i in delivery:
    # 隣の一番近い店の座標を求める
    rightside_shop = shop[bisect.bisect(shop,i)]
    leftside_shop = shop[bisect.bisect(shop,i)-1]

    ans += min(abs(rightside_shop-i),abs(leftside_shop-i))

print(ans)



20　AtCoder Beginner Contest 077 C - Snuke Festival

問題文
atcoder.jp

各段ごとにパターンを列挙していては到底間に合いそうにありません
そこで少し工夫をして解く必要があります

祭壇のうち真ん中の段について残り二つの段については条件が一度に定まることに注目します
中段の祭壇について全探索を行い、条件を満たす上段と下段の組み合わせを二分探索によって求めることで計算を高速にすることができます

pythonでの実装例

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()
c.sort()

ans = 0
C = len(c)

# Bを中心に考える
for i in b:
    ans += (bisect.bisect_right(a,i-1))*(C-bisect.bisect_left(c,i+1))

print(ans)



21　AtCoder Beginner Contest 023 D - 射撃王

問題文
atcoder.jp

すべての風船のペナルティをｐ以下にでき、かつ各風船を割るときの時間が負にならないようなpの値を二分探索で求めます

条件を満たさなかった場合ｐの下限を変更、満たす場合ｐの上限を変更することで最終的に答えを求めることができます

こういった形式の類題として以下の問題も参考になると思います
atcoder.jp

pythonでの実装例

import numpy as np

n = int(input())
h,s = [],[]

for _ in range(n):
    i,j = map(int,input().split())
    h.append(i)
    s.append(j)

h = np.array(h,dtype=np.int64)
s = np.array(s,dtype=np.int64)

# 全てのペナルティをp以下にできるかで二分探索
hi = 10**18
low = 0

def min_pena(p):
    # 各風船のペナルティをｐ以下にするためにかかる時間
    time = (p-h)//s
    time.sort()
    # 各風船の時間がマイナスになっていないかを判定
    return (time >= np.arange(n)).all()

while hi-low > 1:
    mid = (hi+low)//2
    if min_pena(mid):
        hi = mid
    else:
        low = mid

print(hi)



22　AtCoder Regular Contest 054 B - ムーアの法則

問題文
atcoder.jp

様々な解法が考えられる問題ですが、今回は二分探索の解き方でやります
三分探索のpythonに関する解法はじゅっぴーさんのこちらのブログが参考になりました
↓
juppy.hatenablog.com

問題の式は凸関数と凸関数の和なので凸関数になります（解説文引用）
式として書くと
f(x) = x + p\cdot2^{-\frac{2}{3}x} です

これを微分すると
f'(x) = 1- \frac{2p\log 2}{3\cdot2^{\frac{2}{3}x}}

になり、この f'(x)が0を取るようなxの値を求め、 f(x)に代入した答えを2分探索すればOKです

実際には f'(x)=0となるxを計算すると
x = \frac{3}{2}\log_{2} (\frac{2p\log 2}{3})

となるのでこれを代入しても正解を得られます

今回のように微分の式が複雑で解きにくい場合はsympyなどで正解となるxを求めてプログラムに代入するだけでも大丈夫だと思います(REが出るので直接使うことはできませんが)

あとhighの値を極端に大きく設定するとオーバーフローエラーを起こすので注意です


pythonでの実装例

from math import log

p = float(input())

# かかる時間の計算式
def f(x):
    return x+p/2**(2*x/3)

# f'(x) : 微分したもの
def diff(x):
    return 1-2*p*log(2)/(3*2**(2*x/3))
   
high = 10**3
low = 0

# 傾きが0になるxを2分探索（x<0の場合もあるためlow=0に設定）
while high-low > 10**(-10):
    mid = (high+low)/2
    if diff(mid) < 0:
        low = mid
    else:
        high = mid

print(f(high))



23　JOI 2008 本選 3 - ダーツ

問題文
atcoder.jp
※リンク先からさらに問題文のpdfを開く必要があります

ダーツを投げなかった場合を0点として考えます
４本のダーツの得点の組み合わせは０点の時も含めて(n+1)**4通りもあるのでn = 1000の時にTLEを起こしてしまいます

そこで最初に２本投げたときの得点の合計値の可能性を全列挙し、ソートしておきます
その後残りの２本を投げたときの得点の可能性を求めます

この際、「m点を超えないような残り２本の得点の合計（m-i番目の値）が取りうる最大値」を先ほどソートしたリストを使って二分探索します

合計得点がｍを超えなかったもののうち、最大となる得点が答えです

pythonでの実装例

import bisect
from itertools import combinations_with_replacement

n,m = map(int,input().split())
p = [int(input()) for _ in range(n)]+[0] # 投げなかった時の0点も含める

# ダーツ2本の合計得点の組み合わせ全列挙(同じダーツを選ぶ場合があることに注意)
two_darts = [sum(i) for i in combinations_with_replacement(p,2)]
two_darts.sort()

max_point = 0

# m-i以下を満たす範囲での残り2本投げた際の最大得点を求める
for i in two_darts:
    ans = two_darts[bisect.bisect_right(two_darts,m-i)-1]+i

    if ans > m:
        continue

    max_point = max(max_point,ans)

print(max_point)

↓次回　深さ優先探索
algo-archit.hatenablog.com