LoginSignup
56
69

More than 3 years have passed since last update.

@rudorufu1981

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

Last updated at Posted at 2020-05-03

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

ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)

AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

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

過去記事リンク

全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】
全探索：順列全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】
二分探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
幅優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】

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

「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点を前提として、記事を書いていきます！
①二分探索について
まずはけんちょんさんの記事
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
を読んで、二分探索について雰囲気理解する！

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

18　ALDS_4_B - 二分探索

それぞれのset(集合)の積集合のlenを取ってやれば一発だけど、
ここは二分探索で頑張って実装してみる。
二分探索の実装初めてだったけど、
上のサイトの通り実装してみると案外簡単に実装できた！

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のインデックスは同じです！

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 - ピザ

こちらも案外すんなり実装できた！
okのインデックスか、その一個右のインデックスかどちらか近い方からピザを配達してあげればいい。

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を使えるなら使ってあげましょう！
実装が超楽！！！

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

Difficulty:1096
初見で解けませんでした！！！

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

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 - 射撃王

Difficulty:1804！！！青色問題！！！
これも初見で解けませんでした！！！

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

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 - ムーアの法則

Difficulty:1268
これも初見で解けませんでした！！！

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

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

  • x+P*2**(-x/1.5) IMG_9930.JPG
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の値は
このサイト
を使おう！

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

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 - ダーツ

もちろん初見で解けませんでした！！！
というか二分探索ってどこで使うのかの見当も全くつかないw
普通に4重for文やビット全探索ではもちろん無理なので、2本、2本にわけて考える！
N<=1000だと計算量10^6で2重for文まで回せるので、この1000という数字がヒントだったのかなぁ・・・

こちらの記事
AtCoder版！蟻本（初級編） ダーツを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)へ

56
69
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
56
69