[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

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.

Recommended Posts

[At Coder] Solve the problem of binary search
[At Coder] Solve a typical problem of depth-first search (DFS)
Solve the delay of interferometer observation
Illustration of the results of the knapsack problem
Solve the problem of missing libcudart in Ubuntu 16.04 + CUDA 8.0 + Tensorflow environment
Try to solve the N Queens problem with SA of PyQUBO
Solve the initial value problem of ordinary differential equations with JModelica
Solve the subset sum problem with a full search in Python
Use Raspberry Pi to solve the problem of insufficient mobile Wi-Fi connection
How to solve the bin packing problem
Shout Hello, Reiwa! At the beginning of Reiwa
At Coder (2020/09/08)
Solve the traveling salesman problem with OR-Tools
Solve the maximum subarray problem in Python
In search of the fastest FizzBuzz in Python
Python Basic Course (at the end of 15)
Try to solve the fizzbuzz problem with Keras
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
[Python] ABC133B (upper right triangle problem) [At Coder]
Confirmation of basic matters of competition professional ~ Binary search ~
Try to solve the Python class inheritance problem
Solve the knapsack problem using pyomo and glpk
I solved the deepest problem of Hiroshi Yuki.
Solve A ~ D of yuki coder 247 with python
Send Gmail at the end of the process [Python]
Search by the value of the instance in the list
At the time of python update on ubuntu
Remove specific strings at the end of python
ABC146C (binary search)
I investigated the calculation time of "X in list" (linear search / binary search) and "X in set"
Fill at Coder
At Coder # 1 at midnight
The 15th offline real-time I tried to solve the problem of how to write with python
[Python] AGC043A (Problem reading comprehension and DP) [At Coder]
[GoLang] Set a space at the beginning of the comment
In search of the best random dot stereogram (RDS).
Try to solve the problems / problems of "Matrix Programmer" (Chapter 1)
Try to solve the internship assignment problem with Python
Get the image of "Suzu Hirose" by Google image search.
Look at the game records of Go professional Go players
[At Coder] Solving a typical BFS problem [A --Darker and Darker]
I tried to solve the problem with Python Vol.1
Tasks at the start of a new python project
Zip 4 Gbyte problem is a story of the past
Binary search tree is a relative of Hash chain !?
Animate the basics of dynamic programming and the knapsack problem
How to write offline real time I tried to solve the problem of F02 with Python