[PYTHON] [At Coder] Solve the problem of binary search

I want to be a competitive professional, so [This site (AtCoder version! Ant book (beginner))](https://qiita.com/drken/items/e77685614f3c6bf86f44#%E4%BE%8B%E9%A1%8C-2 -5-5warshall-floyd-% E3% 82% 92% E4% BD% BF% E3% 81% 86% E5% 95% 8F% E9% A1% 8C) to solve the AtCoder problem and solve the algorithm The foundation is solidified. This time I solved this problem (C-darts in )is. It is a binary search (complexity O (logN)) that is the basis for competing professionals, but it is quite difficult to determine where to use it. ..

Problem summary

Throw four arrows to find the maximum of the total points hit in $ P_1, P_2, ..., P_N $ that do not exceed $ M $. You can also choose not to throw the arrow. S \leq M 1 \leq N \leq 1000 1 \leq M \leq 2 \times 10^8

solution

• Here has an explanation, but it is summarized for my own understanding. I will.

The first thing that comes to mind is to look at all the patterns in the $ (N + 1) ^ 4 $ way ("+1" is the addition of the arrow P = 0 as a "don't throw" case. ). In other words, it's a full search. It can be implemented just by writing a quadruple loop. However, in this case, the amount of calculation becomes $ O (N ^ 4) $, and AC cannot be performed unless $ N = 100 to 200 $.

So, if you devise something and use ** binary search **, you can solve it in $ O (N ^ 2logN) $ time. This is the method of solution 3 described in the explanation. Instead of "throwing the arrow four times", think of "throwing twice and doing it twice". If you throw the arrow twice, you will get less than $ (N + 1) ^ 2 $. Let's sort this result first as $ Q_1, Q_2, ...., Q_r $. The amount of calculation is $ O (N ^ 2logN) $. → In other words, it can be rephrased as "when the score is r, the total when throwing the arrow twice is M or less". Assuming that the sum of the first two arrows is $ Q_i $, the optimal solution for the sum of the remaining two arrows, $ (Q_j) $, is Q_i + Q_j \leq M Of the $ j $ that satisfy, the one with the largest $ Q_j $ can be found. Such $ j $ can be found in $ O (N ^ 2logN) $ time by binary search. Including the preparation time, it can be calculated in $ O (N ^ 2 logN) $ time as a whole.

Below is an example of an answer using python. The library bisect makes it easy to do a binary search.

import bisect

N, M = map(int, input().split())
p_list = [int(input()) for _ in range(N)]
p_list.append(0)
p_list.sort()
q_list = []

#Create a list of Qi
for i in range(N+1):
    for j in range(i, N+1):  #I try to avoid duplication ... ★
        q = p_list[i] + p_list[j]
        if q <= M:
            q_list.append(q)
q_list.sort()

ans = 0
for q1 in q_list:
    #Binary search(It needs to be right because it is calculated correctly when the total is M)
    insert_index = bisect.bisect_right(q_list, M-q1)
    tmp_ans = q1 + q_list[insert_index-1]
    ans = max(ans, tmp_ans)

print(ans)

By the way, the ★ part in the code,

for i in range(N+1):
    for j in range(N+1): 
        q = p_list[i] + p_list[j]
        if q <= M:
            q_list.append(q)

When I calculated it as and tried to sort it later, it was MLE. Memory is important.