【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】

**目指せ水色コーダー！！！！！！**

ということで、 
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](
https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)(@e869120さん)
>
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

こちらの記事の`初中級者が解くべき過去問精選 100 問`
を**Python**で解いていきます！
@e869120さんに感謝！！！！！！

###過去記事リンク
**全探索：全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】](https://qiita.com/rudorufu1981/items/8ae8beeba7b047f2687c)
**全探索：工夫して通り数を減らす全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】](https://qiita.com/rudorufu1981/items/282e06a6898f021b5e7f)
**全探索：ビット全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
**全探索：順列全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】](https://qiita.com/rudorufu1981/items/71abd5320a636e9146cb)
**二分探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】](https://qiita.com/rudorufu1981/items/2683c3988b246c9cf9ce)
**深さ優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】](https://qiita.com/rudorufu1981/items/e39aa16d73615c7e589f)
**幅優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】](https://qiita.com/rudorufu1981/items/4804987152ad22f3fcb4)

**(2020/05/07 追記)**
※補足
この100問解いてみたシリーズの(**Part6**)の記事から、入力を
`input()`→`sys.stdin.readline().rstrip()`
に変えています！
[【Python】競プロテンプレ【AtCoder】](https://qiita.com/rudorufu1981/items/c6bc5e4d72cfe1cb7f14)
テンプレ用の記事も作ったので、よかったら使ってください〜

#「Part5」〜二分探索編〜
以下の6問を解いていきます！

>
#####二分探索
18　ALDS_4_B - 二分探索　基本問題です。map でも解けますが二分探索で解いてみてください。
19　JOI 2009 本選 2 - ピザ
20　AtCoder Beginner Contest 077 C - Snuke Festival　面白いです。
21　AtCoder Beginner Contest 023 D - 射撃王　教育的に良いです。
22　AtCoder Regular Contest 054 B - ムーアの法則　微分して二分法をすると解けます。三分探索と話が繋がってくるので、それも調べてみると良いと思います。
23　JOI 2008 本選 3 - ダーツ　工夫して二分探索する、チャレンジ問題です。

#二分探索の前提知識
・以下の2点を前提として、記事を書いていきます！
**①二分探索について**
まずはけんちょんさんの記事
[二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜](https://qiita.com/drken/items/97e37dd6143e33a64c8c)
を読んで、二分探索について**雰囲気理解する！**

**②あとは、Pythonの二分探索の具体的な実装方法**
として、
以下のサイトがわかりやすかったので、このサイト
[AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法](https://www.forcia.com/blog/001434.html)
を**じっくり**読んで二分探索について**深く理解する！**


#[18　ALDS_4_B - 二分探索](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja)
それぞれの`set`(集合)の積集合の`len`を取ってやれば一発だけど、
ここは二分探索で頑張って実装してみる。
二分探索の実装初めてだったけど、
上のサイトの通り実装してみると**案外簡単に実装できた！**

```python:test.py
def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
S = LI()
q = I()
T = LI()
ans = 0
def birarysearch(x):
    ok,ng = -1,n
    def is_ok(i):
        return S[i]<=x
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return S[max(ok,0)]==x
for x in T:
    if birarysearch(x):
        ans += 1
print(ans)
```
`ok`のインデックスの最大が答え！
ただしインデックスがマイナスになる場合を注意して、`max(ok,0)`とする！

＜別解＞
ライブラリ`bisect`を使えるなら使ってあげましょう！
**実装がめちゃくちゃ楽！！！**

**上のコードの`ok`のインデックスと、
下のコードの`bisect.bisect(S,x)-1`のインデックスは同じです！**

```python:test.py
import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
S = LI()
q = I()
T = LI()
ans = 0
for x in T:
    ok = bisect.bisect(S,x)-1
    if S[max(ok,0)]==x:
        ans += 1
print(ans)
```
※`bisect.bisect_right`と`bisect.bisect`は全く同じ！！
※`bisect.bisect_left`というものもありますが、基本は`bisect.bisect`しか使わないイメージ！

とにかく
- **`ok`(ライブラリなしバージョン)**
- **`bisect.bisect(A,x)-1`(ライブラリありバージョン)**

**この2つのインデックスは二分探索において鉄板！！！**

#[19　JOI 2009 本選 2 - ピザ](https://atcoder.jp/contests/joi2009ho/tasks/joi2009ho_b)
こちらも**案外すんなり実装できた！**
`ok`のインデックスか、その一個右のインデックスかどちらか近い方からピザを配達してあげればいい。

```python:test.py
def I(): return int(input())
d = I()
n = I()
m = I()
dn = [0]+sorted([I() for _ in range(n-1)])+[d]
mn = sorted([I() for _ in range(m)])
ans = 0
def binarysearch(x):
    ok,ng = -1,len(dn)
    def is_ok(i):
        return dn[i]<=x
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return min(x-dn[ok],dn[ok+1]-x)
for x in mn:
    ans += binarysearch(x)
print(ans)
```
※ちなみに
入力の時に`dn`には、本店情報も入れてあげた`[0]`と`[d]`！！！
これまで無意識によくやってたんですが、
`[0]`とか`[d]`をつけるやり方←**番兵法**って名前がついてるらしいですね〜なんかググったら出てきた。
**貪欲法**もそうだけど、名前を知らずに無意識に習得してるプログラムの考え方他にもありそう！

＜別解＞
こちらもライブラリ`bisect`を使えるなら使ってあげましょう！
**実装が超楽！！！**

```python:test.py
import bisect
def I(): return int(input())
d = I()
n = I()
m = I()
dn = [0]+sorted([I() for _ in range(n-1)])+[d]
mn = sorted([I() for _ in range(m)])
ans = 0
for x in mn:
    ok = bisect.bisect(dn,x)-1
    ans += min(x-dn[ok],dn[ok+1]-x)
print(ans)
```

#[20　AtCoder Beginner Contest 077 C - Snuke Festival](https://atcoder.jp/contests/abc077/tasks/arc084_a)
Difficulty:1096
**初見で解けませんでした！！！**

`bisect.bisect_left`現る・・・
AでもCでもなく**Bを基準にする**発想がなかった・・・
解説をみてなるほど・・・となった問題！
**勉強になりました！！！**

```python:test.py
import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = sorted(LI())
B = sorted(LI())
C = sorted(LI())
ans = 0
for b in B:
    ok_a = bisect.bisect_left(A,b)
    ok_c = bisect.bisect_right(C,b)
    ans += ok_a*(N-ok_c)
print(ans)
```

#[21　AtCoder Beginner Contest 023 D - 射撃王](https://atcoder.jp/contests/abc023/tasks/abc023_d)
**Difficulty:1804！！！青色問題！！！
これも初見で解けませんでした！！！**

解説、とできる人たちのコードをみて、なるほど！となったけど、似たような問題が再度でてきた時に解けますか？と言われたら、まだ解けるイメージがわかないなぁ・・・
**圧倒的な難しい問題の演習量不足！！！**

```python:test.py
import numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
HS = np.array([LI() for _ in range(N)])
H = HS[:,0]
S = HS[:,1]
rangeN = np.arange(N)
ok,ng = 10**9+10**9*10**9+1,0
def is_ok(i):
    T = (i-H)//S
    T.sort()
    return (T>=rangeN).all()
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok)
```
※ライブラリ`bisect`の弱点の一つに配列じゃないと使えない、というのがある。
`h = [i for i in range(10**9+10**9*10**9+1)]`
こんなの書いたら2億%TLEになるので、こういう時ライブラリ`bisect`使えない！
だからライブラリ`bisect`が使えないパターンもあるので、
**二分探索は自前でちゃんと実装できるようになっておく必要あり！**

#[22　AtCoder Regular Contest 054 B - ムーアの法則](https://atcoder.jp/contests/arc054/tasks/arc054_b)
Difficulty:1268
**これも初見で解けませんでした！！！**

`二分法`ならぬ**`三分法`**でとけるみたいです！
単調増加とか単調減少じゃないから、二分探索はできないみたい！
いろいろググりながら実装したけど、雰囲気しか掴めてないw

てかこの問題、最初の式をたてるところでつまずいたのですが・・・
**これもたぶん難しい問題の演習量を積めば、できるようになるはず！！！**
具体的に、かつ0年、1年、2年・・・とじっくり考えれば、式はたてられる！

- `x+P*2**(-x/1.5)`
![IMG_9930.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/ec1a2403-66ed-a7dd-be63-49c736440d40.jpeg)

```python:test.py
def F(): return float(input())
P = F()
high,low = P,0
def f(x):
    return x+P*2**(-x/1.5)
def is_high(i,j):
    return f(i)>=f(j)
while high-low>1*(10**-12):
    mid_right = (high*2+low)/3
    mid_left = (high+low*2)/3
    if is_high(mid_right,mid_left):
        high = mid_right
    else:
        low = mid_left
print(f(high))
```

＜別解＞
ちょっと邪道な気がするけどまあいいやw
1回微分=0のxの値を`x+P*2**(-x/1.5)`に代入すれば答えが求まる。
1回微分=0のxの値は
[このサイト]
(https://ja.wolframalpha.com/input/?i=%28x%2BP*%282**%28-x%2F1.5%29%29%29%27%3D+0)
を使おう！

その結果、
`x≈-2.16404 log(2.16404/P)`
と出てくるので、
あとは、`x+P*2**(-x/1.5)`にxをいれてやるだけ！

```python:test.py
import math
def F(): return float(input())
P = F()
x = -2.16404*math.log(2.16404/P)
def f(x):
    return x+P*(2**(-x/1.5))
print(f(x) if x>0 else f(0))
```

**ACやったぜ！**
ちなみに
前提として`x>=0`(過去には戻れない！)なので最後場合分けしてる。
入出力例2のデバッグ時に場合分けの必要性に気付けると思う！

#[23　JOI 2008 本選 3 - ダーツ](https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c)
**もちろん初見で解けませんでした！！！**
というか二分探索ってどこで使うのかの見当も全くつかないw
普通に`4重for文`やビット全探索ではもちろん無理なので、2本、2本にわけて考える！
`N<=1000`だと計算量`10^6`で`2重for文`まで回せるので、この`1000`という数字がヒントだったのかなぁ・・・

こちらの記事
[AtCoder版！蟻本（初級編） ダーツをpythonで解く](https://qiita.com/mkazuyuki2/items/299f27a9ad34ae78d84f)
を参考にさせていただいて、**無事実装できました！**

```python:test.py
import bisect,itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N,M = LI()
P = [I() for _ in range(N)]
ans = 0
set_two_darts = set()
for x,y in itertools.product(P+[0],repeat=2):
    set_two_darts.add(x+y)
list_two_darts = sorted(set_two_darts)
ok_two_darts = bisect.bisect(list_two_darts,M)-1
if list_two_darts[ok_two_darts]<=M:
    ans = max(ans,list_two_darts[ok_two_darts])
for z in list_two_darts:
    remaining_point = M-z
    if remaining_point<=0:
        continue
    ok = bisect.bisect(list_two_darts,remaining_point)-1
    ans = max(ans,z+list_two_darts[ok])
print(ans)
```

次回は、以下の4問を解いていきます！

>
#####深さ優先探索
24　ALDS_11_B - 深さ優先探索　基本問題です。
25　AOJ 1160 - 島はいくつある？　グラフの連結成分数は、深さ優先探索で計算できます。
26　AtCoder Beginner Contest 138 D - Ki　木構造の問題の多くは、深さ優先探索を使います。
27　JOI 2009 予選 4 - 薄氷渡り　深さ優先探索は、木構造だけではありません、ということを教えてくれる問題です。再帰関数を使って解けます。

Part5/22
おわり！

[次(Part6/22)へ](https://qiita.com/rudorufu1981/items/e39aa16d73615c7e589f)