Solve with Python [100 past questions that beginners and intermediates should solve] (018 --023 Binary search)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "018 --023 Binary Search".

2. Summary

Since python has `` `bisect```, you can use it for binary search, but I thought that you need to practice so that you can write it yourself in order to deal with application problems.

3. Main story

018 --023 Binary search

018. LDS_4_B --Binary Search

Answer

def find_num_by_binary(target_list, num):
    #num is target_Returns whether it is included in the list
    # target_list is assumed to be in ascending order
    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)

I wrote it myself because of the basic problem. The policy of binary search is

1. First, sort the target list in ascending order
2. Let the smallest number be `bottom``` and the largest number be `top```
3. For the time being, set the center (not the exact center because it is divided by 2 and truncated) as `` `middle```, and determine whether or not it matches the target numerical value.
4. If it is judged and does not match, check whether the position of `middle``` is on the ``` bottom``` side or `top``` side
5. If it is on the `bottom``` side, replace the value of top``` with the value of `` middle, and conversely if it is on the `` `top side. Replace the value of `bottom` with the value of `` `middle```
6. Repeat this forever, and when the difference between `bottom``` and `top``` disappears, it's over.
7. Finally, check `bottom``` and top``` just in case, and return `` return``` (maybe you don't have to check it just in case?) is.

019. JOI 2009 Finals 2-Pizza

Answer

import bisect

d = int(input()) #Length of one round of ring
n = int(input()) #Number of stores
m = int(input()) #Number of orders
Stores = [0] + [int(input()) for _ in range(n-1)] #The location of the store. The 0th is the main store.
Stores.sort()
Deliveries = [int(input()) for _ in range(m)] #Delivery destination

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)

Binary search for each delivery destination for an array of stores. The policy is

1. Find in the `bisect_left``` where in the array ``` Stores``` you can insert for each destination (` delivery` ``)
2. Find `distance``` based on the returned left_index ``
3. Keep in mind that `left_index` is greater than or equal to `` `len (Stores) ```. At this time, the main store will also be a candidate store after going around
4. The answer is the sum of the `distance```s for all delivery ``

is.

distanceIt's a pain to think about the subtraction part when calculatingabs()Is used to make it an absolute value. If you judge `left_index` accurately, it seems that it is not necessary to make it an absolute value.

20. AtCoder Beginner Contest 077 C - Snuke Festival

Answer

import bisect
import itertools

N = int(input()) #Number of each part
A = list(map(int, input().split())) #small
B = list(map(int, input().split())) #Moderate
C = list(map(int, input().split())) #large

#C does not need to be sorted
A.sort()
B.sort()

#Binary search for A in each element of B and hold the returned index first
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

#Binary search for B with each element of C. B held above_Take advantage of counts
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

print(total)

Since the list length is `` `10 ** 5``` in the constraint, it seems that the for loop can be turned only once, but first, ignore the constraint and make a policy. The policy is

1. Binary search for `B``` on the element of` C to get the index of the list `` `B
2. Binary search for `` A``` with the elements of `B``` up to this index to get the index
3. The sum of this index is the answer

is. If you drop the above policy into the code, it will be as follows.

#This is TLE
import bisect

N = int(input()) #Number of each part
A = list(map(int, input().split())) #small
B = list(map(int, input().split())) #Moderate
C = list(map(int, input().split())) #large

#C does not need to be sorted
A.sort()
B.sort()

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

print(total)

With this code, the sample will pass, but as N increases, the time will be `` `TLE``` and it will not be in time. So from here, let's think about how to reduce the for loop by one. Thinking "Is there anything that is counted twice?"

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

You can see here that we are counting the same thing over and over again. Therefore, I will consider a method that calculates the numerical value counted here in advance, holds it, and uses it.

As a solution, the only weapons I have at the moment are DP and cumulative sum, so considering using either of them, this time it seems that cumulative sum will work.

#Binary search for A in each element of B and hold the returned index first
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

By holding the value searched for once in two minutes as the cumulative sum in this way, it was not necessary to recalculate each time, and the amount of calculation could be reduced.

021. AtCoder Beginner Contest 023 D --Shooting King

Answer

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)

    #Possible penalties are the minimum value of the initial value H to the maximum value of H after N seconds.
    #Go find the right height in this range

    #Get lower and upper limits
    min_score = min(H)
    max_score = 0
    for i in range(N):
        max_score = max(max_score, H[i] * S[i] * N)

    #Binary search
    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)

Personally, I'm not good at this type of binary search.

If you want to solve it without considering the amount of calculation, for the time being, find all the heights from 0 seconds to N seconds for all balloons, and let the rows be balloons and the columns be seconds `` `N × N``` You can think of creating a matrix and dividing it so that the maximum value is as small as possible. However, since the constraint of N is 10 ** 5, a two-dimensional array cannot be created.

So, let's think about solving in one dimension instead of a two-dimensional array. Instead of thinking about "breaking the maximum value as small as possible", think about looking for "a height that allows all balloons to be broken in time". It is difficult to change this way of thinking.

If you can do this, you can solve it according to the following policy in a 2-minute search.

1. Calculate the `min_score``` and `max_score``` that can be taken because the height is searched.
2. Go to `` `middle_score``` to find the right place between the above two
3. Judgment is made by the function ```is_OK (middle_score, H, S, N) `` `
4. This function determines if all balloons are divisible within `` `middle_score```
5. More specifically, in determining whether or not all balloons can be broken within the time limit (`remain_time```), use True``` and `` False``` return
6. Repeat steps 1-6 to find the right `` `middle_score``` and that's the answer

is.

Regarding the part where the last answer is print, I always wonder whether " max_score "is the answer or" `min_score "is the answer. In such a case, I tried `` `printfor both, and adopted the one that is the sample input. This time it was max_score```.

022. AtCoder Regular Contest 054 B --Moore's Law

Answer

def cal_time(x, P):
    #Calculate the time it takes to use a PC that currently takes P years to calculate after x years
    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))

If you normally solve it as mathematics, you can find the time to differentiate and take the minimum value, so it seems that it is not so difficult (if you are an active student ...). However, when it comes to solving it programmatically, I thought it would be quite difficult if I didn't know how to do it. On the other hand, what I do is not much different from a binary search, and I thought that once I solved it, it would be quite so.

The solution is a ternary search. The policy is

1. Create the desired function ``` cal_time (x, P)` ``
2. Find x, which is the minimum value of this function
3. Gradually shorten the space between the two points `bottom``` and `top```, and find the right point (where the error is within the allowable range).
4. For that purpose, calculate the `middle1``` on the bottom``` side and the `` middle2 on the` `top side, and use the function `` `cal_time (x). , P) ``` to compare sizes
5. As a result of the above comparison, replace the one with the larger value calculated on the `` bottom``` side and the ``` top``` side with `middle```.
6. Repeat the above and end the search when an acceptable error is reached.
7. Finally, calculate the time with `bottom``` or `top``` (it doesn't matter because it is reduced to the error), and that is the answer.

is.

023. JOI 2008 Finals 3-Darts

Answer

import bisect

N, M = map(int, input().split()) #N is the number of target breaks (the number of elements of P), M is the bar for scoring points
#If the total score S is M or less, it will be S, and if it is over M, it will be 0 points.->Just give the total value at the last minute
P = [int(input()) for _ in range(N)] #Each target score
P.append(0) #Include 0 points when not throwing
P.sort()
double_score_list = []

for p1 in P:
    for p2 in P:
        score = p1 + p2
        if score > M: #Prevent useless append
            break 
        double_score_list.append(score)
double_score_list.sort()

#Binary search for yourself
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)

The first thing that comes to mind is to create a list of points that can be earned from a given `P``` and then use a binary search to find the right score that does not exceed M```. But this requires four for loops to create the list, which is unlikely to be in time given that `` N is `` 10 ** 3. You need to reduce the for loop to at most two.

Considering reducing the for loop to two, throwing four times is likely to be halved if divided into two. It seems that you should make a list of points that can be obtained in 2 times, including the points if you do not throw, and search for the right score in a 2-minute search for each score.

The specific policy is

1. Create a list of points `` `double_score_list``` that can be obtained in 2 times, including the points (0 points) when not throwing
2. At this time, put `break``` so that the list does not include points that are duplicated or exceed `M```.
3. Perform a binary search on all elements of double_score_list to find the maximum score below M

is.