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.
ABC 060 B - Choose Integers
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.
1≦A≦100 1≦B≦100 0≦C<B
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.
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.
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)
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
ABC 081 B - Shift only
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.
N=3 A=16,12,24 Answer: 2
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.
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?
K, S=2, 2 Answer: 6
There are 6 sets of X, Y, Z that satisfy the condition of the question sentence.
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)
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