Pythonで解く【初中級者が解くべき過去問精選 100 問】(018 - 023 二分探索)

# 1. 目的
[初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa)をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「018 - 023 二分探索」です。

# 2. 総括
pythonには```bisect```があるのでそれを使えば二分探索はできますが、応用問題に対応するためには自分で書けるように練習する必要があると思いました。


# 3. 本編

## 018 - 023 二分探索

### 018. [LDS_4_B - 二分探索](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/997cc877-0f32-02b6-c19a-7d3756a95e54.png)

#### 回答
```python

def find_num_by_binary(target_list, num):
    # numがtarget_listに含まれているか否かを返す
    # target_listは昇順であることが前提
    bottom = 0
    top = len(target_list) - 1

    while top - bottom > 1:
        middle = (top + bottom) // 2
        if num == target_list[middle]:
            return True

        if num > target_list[middle]:
            bottom = middle
        else:
            top = middle
        
    if target_list[bottom] == num or target_list[top] == num:
        return True
    else:
        return False

if __name__ == "__main__":
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    count = 0
    for t in T:
        count += find_num_by_binary(S, t)
    
    print(count)

```
基礎問題のため自分で書きました。
二分探索の方針は
1. まずはターゲットとなるリストを昇順に並べる
2. 一番小さい数字を```bottom```、一番大きい数字を```top```とする
3. とりあえず、中央らへん(2で割って切り捨てているので正確な中央ではない)を```middle```として、目的となる数値と一致しているか否かを判定する
4. 判定して一致していない場合、```middle```の位置が、```bottom```側にあるかそれとも```top```側にあるかをチェック
5. ```bottom```側にある場合は```top```の値を```middle```の値に置き換え、逆に```top```側にある場合は```bottom```の値を```middle```の値に置き換える
6. これを永遠と繰り返し、```bottom```と```top```の差がなくなったら終わり
7. 最後に```bottom```と```top```を念のため調べて、```return```を返す(念のためなので調べなくてもよいかも？)
です。


---

### 019. [JOI 2009 本選 2 - ピザ](https://atcoder.jp/contests/joi2009ho/tasks/joi2009ho_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e9fdd5db-c65f-4314-b963-985ff64c93d7.png)


#### 回答
```python

import bisect

d = int(input()) # 環状1周の長さ
n = int(input()) # 店の数
m = int(input()) # 注文の数
Stores = [0] + [int(input()) for _ in range(n-1)] # 店舗の位置。0番目は本店。
Stores.sort()
Deliveries = [int(input()) for _ in range(m)] # 宅配先

total_distance = 0
for delivery in Deliveries:
    left_index = bisect.bisect_left(Stores, delivery)

    if left_index >= len(Stores):
        distance = min(abs(d - delivery), abs(delivery - Stores[left_index-1]))
    else:
        distance = min(abs(Stores[left_index] - delivery), abs(delivery - Stores[left_index-1])) 

    total_distance += distance

print(total_distance)


```
店の配列をについて各配達先を二分探索します。
方針は、
1. 各配達先（```delivery ```）について配列```Stores```のどの位置に挿入できるか```bisect_left```で探します
2. 返ってきた```left_index ```をもとに```distance```を求めます
3. 留意すべきは、```left_index ```が```len(Stores)```以上になる際です。この時は一周回って本店も候補店舗になります
4. すべての```delivery ```についての```distance```を足しあげたものが答え

です。


```distance``` を計算する際の引き算の個所は、考えるのがめんどくさいのですべて```abs()```を使って絶対値にしています。
正確に```left_index ```を判定してやれば、絶対値にする必要ないと思われます。

---

### 020. [AtCoder Beginner Contest 077 C - Snuke Festival](https://atcoder.jp/contests/abc077/tasks/arc084_a)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/2c87b93c-76a9-70d5-ced3-2c0d92ce4035.png)

#### 回答
```python
import bisect
import itertools

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

# Cの各要素でBを二分探索。上記で保有しておいたb_countsを活用する
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

print(total)

```

制約にリスト長さが```10**5```とありますので、forループは1回しか回せそうにないですが、まずは制約を無視して方針を立てます。
方針は、
1. ```C```の要素で```B```を二分探索して、リスト```B```のインデックスを取得
2. このインデックスまでの```B```の要素でさらに```A```を二分探索してインデックスを取得
3. このインデックスの合計が答え

です。 
上記の方針をコードに落とすと下記となります。

```python
# これはTLE
import bisect

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

total = 0
for c in C:
    b_count = bisect.bisect_left(B, c) # bの数量
    for b in B[:b_count]:
        a_count = bisect.bisect_left(A, b) # aの数量
        total += a_count

print(total)

```

このコードだと、サンプルは通りますが、Nが大きくなると時間が```TLE```となり間に合いません。
なのでここからforループを1つ減らす方法を考えます。
「重複して数え上げているものはないか」と考えると、

```python

for b in B[:b_count]:
        a_count = bisect.bisect_left(A, b)
```

ここで何度も同じものを数えていることがわかります。
なのでここで数えている数値を事前に計算して保有しておき、それを使うような方法を考えます。

解決策として僕が現時点で持っている武器はDPと累積和くらいですのでそのどちらかを使うことを考えると、今回は累積和で上手くいきそうです。

```python

# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

```

このように一回二分探索した値を累積和として保有しておけば、毎回計算しなおさなくてよくなり計算量を減らすことができました。


---

### 021. [AtCoder Beginner Contest 023 D - 射撃王](https://atcoder.jp/contests/abc023/tasks/abc023_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/f1973d27-2bce-65e4-11f6-8dbb08896c51.png)

#### 回答
```python

def is_OK(middle_score, H, S, N):
    remain_times = []
    for i in range(N):
        remain_time = (middle_score - H[i]) / S[i]
        remain_times.append(remain_time)
    remain_times.sort()

    for time, remain_time in enumerate(remain_times):
        if remain_time < time:
            return False
    
    return True

if __name__ == "__main__":
    N = int(input())
    H = []
    S = []
    for _ in range(N):
        h, s = map(int, input().split())
        H.append(h)
        S.append(s)

    # 取りうるペナルティは初期値Hの最小値～N秒後のHの最大値
    # この範囲の中でちょうどよい高さを探しに行く

    # 下限と上限を取得
    min_score = min(H)
    max_score = 0
    for i in range(N):
        max_score = max(max_score, H[i] * S[i] * N)

    # 二分探索実施
    while max_score - min_score > 1:
        middle_score = (max_score + min_score) // 2

        if is_OK(middle_score, H, S, N):
            max_score = middle_score
        else:
            min_score = middle_score
    
    print(max_score)

```

個人的にはこの形式の二分探索はやや苦手です。

計算量を考えずに解くとすれば、とりあえずすべての風船について0秒後からN秒後までの高さをすべて求めて、行が風船、列が秒とする```N × N```行列を作成し、最大値をできるだけ小さくするように割っていくことを考えればよさそうです。
しかし、Nの制約が10**5なので2次元配列は作成できません。

なので、2次元配列ではなく1次元で解くことを考えます。
「最大値をできるだけ小さくするように割る」ことを考えるのではなく、「すべての風船を時間内にちょうど割ることができるような高さ」を探すことを考えます。
この考え方の変換が難しいです。

ここができれば、2分探索で下記の方針の通り解きます
1. 高さを探すのでとりうる```min_score```と```max_score```を算出しておく
2. 上記二つの間でちょうどよいとこを```middle_score```で探しに行く
3. 判定は関数 ```is_OK(middle_score, H, S, N)``` で行う
4. この関数は、すべての風船を```middle_score```内で、割り切れるか否かを判定するもの
5. より具体的には、判定にあたっては、制限時間（```remain_time```）内にすべての風船を割れるか否かを```True```、```False```で返します
6. 1~6を繰り返してちょうどよい```middle_score```を見つけて、それが答え

です。

最後の答えを```print```する部分について、いつも「```max_score```」が答えなのかそれとも「```min_score```」が答えなのかを迷います。
そんな時は、とりあえずどちらも```print```してみて、サンプル入力であってるほうを採用しています。
今回は```max_score```でした。


---

### 022. [AtCoder Regular Contest 054 B - ムーアの法則](https://atcoder.jp/contests/arc054/tasks/arc054_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/ebf93818-1ea4-64eb-9046-416f1441a9dd.png)

#### 回答
```python

def cal_time(x, P):
    # 現在計算にP年かかるPCをx年後に使用してかかる時間を算出
    return x + P * pow(2, -x/1.5)

if __name__ == "__main__":
    tolerance = 10**(-8)
    P = float(input())

    bottom = 0
    top = 10**18 + 1

    while top - bottom > tolerance:
        middle1 = (2 * bottom + top) / 3
        middle2 = (bottom + 2 * top) / 3

        if cal_time(middle1, P) < cal_time(middle2, P):
            top = middle2
        else:
            bottom = middle1
    
    print(cal_time(bottom, P))

```

普通に数学として解くのであれば微分して極小値をとる時間を求めればよいのでそこまで難しくないと思われます（現役学生であれば・・・）。
しかし、プログラムで解くとなるとやり方を知らなければ、なかなか難しいと思いました。
一方で、やることは二分探索とあまりかわらず、一度解けば何とかなりそう、と思いました。

解き方は三分探索です。
方針は、
1. 目的となる関数```cal_time(x, P)```を作成
2. この関数の極小値となるxを探します
3. ```bottom```と```top```の2点間を徐々に縮めていき、ちょうどよい(誤差が許容範囲になる)箇所が求めたいxとなります
4. そのために```bottom```側の三分点```middle1```と```top```側の```middle2```を算出し関数```cal_time(x, P)```で大きさを比べます
5. 上記比較の結果、```bottom```側と```top```側で大きい値が算定されたほうを```middle```に置き換えます
6. 上記を繰り返し、許容される誤差になったら探索終了
7. 最後に```bottom```又は```top```で時間を算出（誤差まで下げているのでどっちでもよい）し、それが答え

です。


---

### 023. [JOI 2008 本選 3 - ダーツ](https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/8444db8f-1e35-4eee-974b-408758932224.png)

#### 回答
```python

import bisect

N, M = map(int, input().split()) # Nは的の区切り数（Pの要素数）、Mは得点を獲得する際のバー
# 得点の合計SがM以下の場合はS、M超の場合は0点になる -> ぎりぎりの合計値を出せばよい
P = [int(input()) for _ in range(N)] # 各的の点数
P.append(0) # 投げない場合の0点も含めておく
P.sort()
double_score_list = []

for p1 in P:
    for p2 in P:
        score = p1 + p2
        if score > M: # 無駄なappendを防ぐ
            break 
        double_score_list.append(score)
double_score_list.sort()

# 自分自身を二分探索する
answer = 0
for double_score in double_score_list:
    target = M - double_score
    max_i = bisect.bisect_left(double_score_list, target) - 1

    score = double_score + double_score_list[max_i]
    if score > M:
        continue
    answer = max(answer, double_score + double_score_list[max_i])

print(answer)


```

まず思いつくのは、与えられた```P```から獲得することができる得点のリストを作成し、```M```を超えないちょうどよい得点を二分探索で探す方法です。
しかしこれではリストを作成するためにforループを4回まわす必要があり、```N```が```10**3```であることを考えると間に合いそうにありません。forループを多くとも2つにまで減らす必要があります。

forループを2つに減らすことを考えると、4回投げることを2回ずつに分けて考えれば半分になりそうです。
投げない場合の点数を含めて、2回で獲得することができる得点のリストを作成し、それぞれの得点について2分探索でちょうどよい得点を探しにいけばよさそうです。

具体的な方針は、
1. 投げない場合の得点（0点）も含めて、2回で獲得できる得点のリスト```double_score_list```を作成する
2. この際、重複や```M```を超過するような得点をリストに含めないように```break```を入れておく
3. ```double_score_list```のすべての要素について二分探索を行い、合計が```M```以下で最大となる得点を探す

です。


---