[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]

** Aim for a light blue coder! !! !! !! !! !! ** **

So [Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( 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 has collected 100 good educational questions that are appropriate for brown and green coders to achieve a light blue coder, or rating 1200, with a small number of questions.

100 past questions that beginners and intermediates should solve in this article` Will be solved with ** Python **! Thanks to @ e869120! !! !! !! !! !!

Past article link

** Search all: List all ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22] ** Full search: All enumeration to reduce the number of streets by devising ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] ** Full search: Bit full search ** [[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Full search: Permutation full search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part4 / 22] ** Binary search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part5 / 22] ** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22] ** Breadth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]

** (Added on 2020/05/07) **

• Supplement Enter from the (** Part 6 **) article in this 100-question series input()→sys.stdin.readline().rstrip() I'm changing to! [Python] Competitive template [At Coder] I also made an article for the template, so please use it if you like ~

"Part 5" ~ Binary Search ~

We will solve the following 6 questions!

Binary search

18 ALDS_4_B --Binary search This is a basic problem. You can solve it with map, but try solving it with a binary search. 19 JOI 2009 Final 2 --Pizza 20 AtCoder Beginner Contest 077 C --Snuke Festival Interesting. 21 AtCoder Beginner Contest 023 D --Shooting King Educationally good. 22 AtCoder Regular Contest 054 B --Moore's Law It can be solved by differentiating and dichotomizing. The story is connected to the ternary search, so I think you should check that as well. 23 JOI 2008 Final Round 3-Darts This is a challenge problem that you can devise and search for in two.

Prerequisite knowledge of binary search

・ I will write an article based on the following two points! ** ① About binary search ** First of all, Kencho's article Generalization of binary search algorithm-Recommendation of binary search method- Read about the binary search ** Understand the atmosphere! ** **

** ② After that, a concrete implementation method of Python binary search ** As The following site was easy to understand, so this site AtCoder Must-see for gray, brown and green people! How to write a binary search without making it buggy ** Carefully ** Read about binary search ** Deeply understand! ** **

18 ALDS_4_B --Binary search

If you take the len of the intersection of each set (set), it will be one shot, I will do my best to implement this with a binary search. It was my first time to implement a binary search, When I implemented it according to the above site ** It was unexpectedly easy to implement! ** **

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)

The largest index of ʻokis the answer! However, be careful when the index becomes negative, and set it tomax (ok, 0)`!

Another solution
If you can use the library bisect, let's use it! ** Implementation is insanely easy! !! !! ** **

** With the ʻokindex in the code above, The index ofbisect.bisect (S, x) -1` in the code below is the same! ** **

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 and bisect.bisect are exactly the same! !!
• There is also bisect.bisect_left, but the basic image is that only bisect.bisect is used!

Anyways -** ʻok(version without library) ** -**bisect.bisect (A, x) -1` (version with library) **

** These two indexes are iron plates in binary search! !! !! ** **

19 JOI 2009 Finals 2-Pizza

This was also ** unexpectedly easy to implement! ** ** You can deliver the pizza from the index of ʻok` or the index to the right of it, whichever is closer.

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)

• By the way At the time of input, dn also included the head office information,[0]and[d]! !! !! I used to do it unconsciously, but How to add [0] or [d] ← ** It seems that it has a name called "Banbeiho **". As with ** Greedy algorithm **, there may be other ways of thinking about programs that you unknowingly learn without knowing your name!

Another solution
If you can use the library bisect, let's use it too! ** Easy to implement! !! !! ** **

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 ** I couldn't solve it at first sight! !! !! ** **

bisect.bisect_left appears ... There was no idea ** based on ** B, not A or C ... As you can see from the explanation, the problem became ...! **I learned a lot! !! !! ** **

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 --Shooting King

** Difficulty: 1804! !! !! Blue problem! !! !! I couldn't solve this at first sight! !! !! ** **

Look at the code of the people who can explain it, I see! But can you solve it when a similar problem comes up again? If you say that, I still don't know the image that can be solved ... ** Insufficient amount of exercises for overwhelmingly difficult problems! !! !! ** **

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)

• One of the weaknesses of the library bisect is that it can only be used with arrays. h = [i for i in range(10**9+10**9*10**9+1)] If you write something like this, it will be 200 million% TLE, so you can't use the library bisect at such times! Therefore, there are some patterns that the library bisect cannot be used, so ** You need to be able to implement binary search properly on your own! ** **

22 AtCoder Regular Contest 054 B --Moore's Law

Difficulty:1268 ** I couldn't solve this at first sight! !! !! ** **

It's not a dichotomy ** It seems that it can be solved by the three-division method **! It's not a monotonous increase or a monotonous decrease, so it seems that you can't do a binary search! I implemented it while googled variously, but I can only grasp the atmosphere w

I stumbled upon this problem when I was formulating the first formula ... ** This should probably be possible with a lot of exercises on difficult problems! !! !! ** ** If you think about it concretely and for 0 years, 1 year, 2 years ...

• x+P*2**(-x/1.5)

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))

Another solution
I feel a little wicked, but no w The answer can be obtained by substituting the value of x with the first derivative = 0 into x + P * 2 ** (-x / 1.5). The value of x with one derivative = 0 is [This site] (https://ja.wolframalpha.com/input/?i=%28x%2BP*%282**%28-x%2F1.5%29%29%29%27%3D+0) Let's use!

as a result, x≈-2.16404 log(2.16404/P) Because it comes out After that, just put x in x + P * 2 ** (-x / 1.5)!

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))

** I did AC! ** ** By the way As a premise, x> = 0 (I can't go back to the past!), So I'll separate the last cases. You will notice the need for case-by-case when debugging I / O Example 2!

23 JOI 2008 Finals 3-Darts

** Of course I couldn't solve it at first sight! !! !! ** ** Or rather, I have no idea where to use binary search w Of course, it is impossible to do a quadruple for sentence or a full bit search, so think about it in two or two! If N <= 1000, the amount of calculation 10 ^ 6 can be turned up to double for statement, so I wonder if this number 1000 was a hint ...

This article AtCoder version! Ant book (beginner) Solve darts with python I was able to implement it safely by referring to **! ** **

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)

Next time, I will solve the following 4 questions!

Depth-first search

24 ALDS_11_B --Depth-first search This is a basic problem. 25 AOJ 1160-How many islands are there? The number of connected components in the graph can be calculated by depth-first search. 26 AtCoder Beginner Contest 138 D --Ki Many tree structure problems use depth-first search. 27 JOI 2009 Qualifying 4-Thin ice migration Depth-first search is not just a tree structure, it is a problem that tells us. It can be solved using a recursive function.

Part5/22 end!

Next (Part 6/22)