Master linear search! ~ Python implementation version ~

Introduction

This is Qiita's first post for a beginner who has been in competitive programming (AtCoder) for 2 months to study programming. This article was created by @drken Mastering Linear Search! ~ Knowing that you can do various things with for statements ~ This is for you to understand the wonderful article. Also, I will post it as a reference for people similar to me by posting an implementation example in Python. Please be careful about spoilers as we will post some examples of AtCoder problems. I would be very grateful if you could give me guidance if there are any unsightly points.

Find one that meets the conditions

ABC 060 B - Choose Integers

Problem statement

You choose some positive integers and sum them up. There is no limit to the number of numbers you can choose or the number of integers you can choose. You can choose as large an integer as you like, or you can choose 5000 trillion integers. However, all numbers you choose must be multiples of A. Also, at least one must choose an integer. And I want to make C the sum of the sum divided by B. Please judge whether you can choose an integer like this. Output YES if possible, NO otherwise.

Constraint

1≦A≦100 1≦B≦100 0≦C<B

Numerical example

A, B, C = 7,5,1 Answer: YES For example, if you select 7,14, the total sum will be 21, and if you divide this by 5, you will get 1.


Commentary

I think it is a typical example of judgment by flag management. The problem statement says "to find the sum of the sum divided by B", but since it means dividing the sum of multiples of A, that is, dividing the multiple of A by B gives the remainder. Therefore, since the maximum amount of calculation is 100 * 100, the entire search is straightforward.

a, b, c = map(int, input().split())
ans = 'NO'              #Hold the initial value of the judgment flag as NO
for i in range(101):    #I want to multiply the maximum input value of 100 by a multiple, so 100+1
    if a*i % b == c:    #Implement problem statement judgment with if
        ans = 'YES'     #If the judgment of the if statement becomes True, change the answer to YES
        print(ans)      #Output YES if the if statement judgment is True
        exit()          #Since it is sufficient to output any one, stop with judgment True
print(ans)              #If the judgment of the if statement is False, NO is output with the initial value.

Know where to find the ones that meet the conditions

Set an index in the previous code to determine the location. This time, the purpose is to know the multiple of input A. The result is # YES 3.

a, b, c = map(int, input().split())
ans = 'NO'
idx = 0                 #The initial value is 0 to know the multiple
for i in range(101):
    if a*i % b == c:
        ans = 'YES'
        idx = i         #Holds a multiple that makes the judgment of the if statement True
        print(ans, idx) #If the judgment of the if statement becomes True, YES and a multiple are output.
        exit()
print(ans, idx)         #If the judgment of the if statement is False, NO and 0 are output with the initial values.

It is also possible to know the position using enumerate. In this case, we need to give an iterable object, so we created the list in advance. The result is also # YES 3.

a, b, c = map(int, input().split())
multiple = [x for x in range(101)]
ans = 'NO'
for idx, i in enumerate(multiple):
    if a*i % b == c:
        ans = 'YES'
        print(ans, idx)
        exit()
print(ans, idx)

Find the minimum value, find the maximum value

In Python, you can create a list and use the min and max functions to find it. If the list is slow, using set seems to make it explosive. Matter that became explosive just by changing from "in list" to "in set" in Python and the reason

lst = [i for i in range(-5, 6)]
print(lst)       # [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
print(min(lst))  # -5
print(max(lst))  # 5

Count those that meet the conditions

ABC 081 B - Shift only

Problem statement

N positive integers A1,…, A2,…, AN are written on the blackboard. Sunuke can perform the following operations when all the integers written on the blackboard are even numbers.

--Replace all the integers written on the blackboard with the ones divided by two.

Please ask how many times you can perform the operation at the maximum.

Constraint

Numerical example

N=3 A=16,12,24 Answer: 2


Commentary

If all the values in the list are even, the number is incremented by 1. It is a problem that is easier to understand if it is implemented with while, but I dare to implement it with for. The maximum value of A is 10 ^ 9, but it must be an even number, so I think that it is enough to repeat it up to 31623 times with √10 ^ 9 (the amount of calculation is rough because there is no sense of mathematics).

n = int(input())
a = list(map(int, input().split()))
cnt = 0                              #Flag to manage enumeration
for _ in range(31623):               # _Prepare an empty argument for repeated execution with
    if all(i % 2 == 0 for i in a):   #Pass list a to i, and all to determine if everything is even
        cnt += 1                     #Increment the number of times 1 to cnt if the condition is met
        a = [i//2 for i in a]        #Divide each element of list a by 2 and return to list a
print(cnt)                           #Outputs the numerical value counted by incrementing

This is an implementation example in a while statement. This is simpler, isn't it?

n = int(input())
a = list(map(int, input().split()))
cnt = 0

while all(i % 2 == 0 for i in a):
    cnt += 1
    a = [i//2 for i in a]
print(cnt)

ABC 051 B - Sum of Three Integers This is an example not found in @ darken's article, but I think it's a good question, so I'll write it here. The problem is to find the number of combinations. It is a problem packed with the essence necessary for understanding the movement of multiple loops of for, considering the amount of calculation, setting the range of conditional statements, and competing pros.

Problem statement

Two integers K and S are given. It has three variables X, Y, Z and takes an integer value that satisfies 0 ≤ X, Y, Z ≤ K. How many values can be assigned to X, Y, Z that satisfy X + Y + Z = S?

Constraint

Numerical example

K, S=2, 2 Answer: 6

There are 6 sets of X, Y, Z that satisfy the condition of the question sentence.


Commentary

X, Y, Z are each within the range of K. Therefore, create a triple loop of X, Y, Z with k + 1 (maximum 2500), and if the total of the combinations becomes S, increment it as the number of times 1.

k, s = map(int, input().split())
ans = 0                       #Flag to count the number that meets the criteria
for x in range(k+1):          #Since the entire range of k is searched, the range range of x is k+1
    for y in range(k+1):      #Same as above
        for z in range(k+1):  #Same as above
            if x+y+z == s:    #Set the condition of the question sentence
                ans += 1      #If the if judgment is True, increment 1
print(ans)                    #Output the number that matches the condition

In the above example, the answer is correct, but the larger the value, the longer the execution time is. I have to try up to 2500 ^ 3 = 15625000000 ways, so I can't make it in time. Therefore, it is necessary to devise ways to reduce the amount of calculation.

If it is 2500 ^ 2, there will be 6250000 ways, so it seems to be in time. Therefore, consider reducing the number of loops by one.

Of the combinations of X, Y, and Z, Z will be the value subtracted from S once X and Y are determined. However, if you implement it under that condition obediently, the number of combinations will be nine.

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if x+y+z == s:
            ans += 1
print(ans)

This is because, for example, if X = 2 and Y = 2, then S = 2 unless Z = −2. Therefore, Z must be greater than or equal to 0 and within the range of K. If you add this to the conditional statement, the answer is 6. I was able to find the correct answer while reducing the number of loops by one.

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k and x+y+z == s:
            ans += 1
print(ans)

in conclusion

We would like to thank @drken for writing a number of great articles, our seniors, and AtCoder for providing a place to enjoy programming. Thank you for reading to the end.

Recommended Posts

Master linear search! ~ Python implementation version ~
Linear search in Python
Breadth-first search / bidirectional search (Python version)
Algorithm learned with Python 9th: Linear search
PYTHON2.7 64bit version
"Linear regression" and "Probabilistic version of linear regression" in Python "Bayesian linear regression"
Implementation example of simple LISP processing system (Python version)
Sequential search with Python
RNN implementation in python
Python Exercise 1-Breadth-first search
[Python] Search (itertools) ABC167C
Binary search in Python
A python implementation of the Bayesian linear regression class
[Python] Search (NumPy) ABC165C
[Python] Binary search ABC155D
python bit full search
Binary search with python
Binary search with Python3
Search Twitter using Python
Overview of generalized linear models and implementation in Python
Python version switching (pyenv)
Binary search in Python (binary search)
SVM implementation in python
Check version with python
[Internal_math version (2)] Decoding the AtCoder Library ~ Implementation in Python ~
Aim python library master (48) autopep8
Aim python library master (36) json2html
Aim python library master (49) psidialogs
Aim python library master (26) easyxml
Aim python library master (29) table_printer
Aim python library master (55) namespaces
Aim python library master (46) browserplus
Aim python library master (30) chronyk
Aim python library master (3) workalendar
Aim python library master (37) slimurl
Aim python library master (44) pynetviz
Aim python library master (8) rolex
Aim python library master (52) marktime
Aim python library master (7) numparser
Aim python library master (21) hy
Aim python library master (18) requests
Aim python library master (13) easydev
Aim python library master (20) pyyaml
Aim python library master (34) concurrent
Aim python library master (40) wordsegmentation
[Line / Python] Beacon implementation memo
Aim python library master (43) cpmoptimize
Aim python library master (68) pazudorasolver
Search for strings in Python
Aim python library master (11) nlist
Aim python library master (38) beautiful_print
Aim python library master (65) geopy
Aim python library master (2) vincenty
Aim python library master (59) logbook
Aim python library master (51) pyautogui
Aim python library master (10) timeit
Search algorithm using word2vec [python]
Homebrew Python --Youtube Search Program
[Python] DFS (Depth-first Search) ATC001A
Change python version using pyenv
Aim python library master (0) Links