[Kenchon book to Python]-Chapter 3- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!

Introduction

This article is Kencho-san's book, which contains many explanations of competitive programming, ** Train your problem-solving skills! Algorithms and data structures（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。

On this page, we will introduce the contents of Chapter 3! Please forgive me if there are any bugs.

See the following pages for links to other chapters. [Table of Contents Page] https://qiita.com/KevinST/items/002676619a583754bf76

code3.1 Linear search method

It's the one that "let's check in order from the front"!

code3-1.py

#Receive input
N, v = map(int, input().split())
a = list(map(int, input().split()))

#Linear search
exist = False
for i in range(N):
    if a[i] == v:
        exist = True

#Result output
if exist:
    print("Yes")
else:
    print("No")

[Input example] 5 1 2 3 4 1 11 [Output example] Yes

code3.2 Get the "subscript" that has a specific element

Now it's time to get the index.

code3-2.py

#Receive input
N, v = map(int, input().split())
a = list(map(int, input().split()))


##Linear search##
found_id = -1
for i in range(N):
    if a[i] == v:
        found_id = i
        break
print(found_id)

[Input example] 4 2 0 2 -1 11 [Output example] 1

For the number "2" a[0]: 0 a[1]: 2 ... I will look for it. This time, a [1] = 2, and the number we were looking for here matches a [i]. Break here and output.

code3.3 Find the minimum value

code3-3.py

#Receive input
N = int(input())
a = list(map(int, input().split()))


##Linear search##
#Set the initial value of the minimum value to "infinity"
min_value = float("inf")
for i in range(N):
    if a[i] < min_value:
        min_value = a[i]
print(min_value)

[Input example] 4 0 2 -1 11 [Output example] -1

I was able to find the smallest value "-1". The amount of calculation is $ O (N) $.

code3.4 Find the minimum value of the pair sum (range of K or more)

Select one element from array a and one element from array b and add them to make a number. Among them, choose the one with K or more and the smallest one.

code3-4.py

#Receive input
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

#Linear search
min_value = float("inf")
for i in range(N):
    for j in range(N):
        #If the sum is less than K, discard it
        if a[i] + b[j] < K:
            continue
        #Update minimum
        if a[i] + b[j] < min_value:
            min_value = a[i] + b[j]
print(min_value)

[Input example] 4 10 1 2 5 6 7 12 16 22 [Output example] 12

code3.5 Determines whether the subset represented by the integer bit contains the i-th element

This is the preparation for the so-called bit full search. I also added input and output to check the operation.

code3-5.py

#Receive input
i = int(input())
bit = int(input(), 2)

#Check if the subset represented by bit contains the i-th element
if bit & (1 << i):
    print("Yes")
else:
    print("No")

[Input example] 1 1010 [Output example] Yes

Bit full search is one of the full search methods, and can enumerate all ON / OFF patterns. For details, see Kencho-san's book and online commentary.

For those who say "Bi, bit ... No, it's difficult> <", you can use the Python function to search all without thinking about bit. (See "3.6 Supplement")

code3.6 Full search method using bits for the partial sum problem

It is a bit full search.

code3-6.py

#Receive input
N, W = map(int, input().split())
a = list(map(int, input().split()))

#bit is 2^Moves through n subsets
exist = False
for bit in range(2**N):
    #The sum of the elements contained in the subset
    sum_val = 0
    for i in range(N):
        #i-th element a[i]Is included in the subset
        if bit & (1 << i):
            sum_val += a[i]

    #sum_Whether val matches W
    if sum_val == W:
        exist = True

if exist:
    print("Yes")
else:
    pritn("No")

[Input example] 4 10 1 9 100 200 [Output example] Yes

Consider a subset (1,9). Since its sum is 10, it matches W. So the answer is "Yes".

code3.6 Supplement: All enumeration using itertools.combinations

bit it's hard! For those who say, we have prepared another ver. As a procedure

1. 1. Decide how many pieces to take out from the array (0 to N pieces)
2. Consider that the number determined by 1 is taken out from an array of N elements. List all patterns to be extracted 0: [] 1 piece: [a0], [a1], [a2] ... 2 pieces: [a0, a1], [a0, a2], ..., [aN-1, aN] ** * Use the combinations function in Python's convenient library itertools **

Python is good! (Promotion)

code3-6-another_ver.py

from itertools import combinations
N, W = map(int, input().split())
a = list(map(int, input().split()))

exist = False

#Determine the number of elements to retrieve (num_of_a): 0 to N
for num_of_a in range(N+1):
    #From a, all num_of_Extract elements with a extraction method and store each in the variable pattern
    for pattern in combinations(a, num_of_a):
        #Calculate total
        sum_val = sum(list(pattern))
        #sum_Whether val matches W
        if sum_val == W:
            exist = True

if exist:
    print("Yes")
else:
    pritn("No")

[Input example] 4 10 1 9 100 200 [Output example] Yes

If you want to know more about itertools, the following page may be helpful. If you read it, you will be impressed by the convenience of the Python standard library! Wow, itertools

Click here for Chapter 4 https://qiita.com/KevinST/items/f846d57e56242c6e1293