[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. Decide how many pieces to take out from the array (0 to N pieces)
  1. 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

Recommended Posts

[Kenchon book to Python]-Chapter 3- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
[Kenchon book to Python]-Chapter 2- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
[Kenchon book to Python]-Chapter 4-"Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
[Kenchon book to Python] "Train your problem-solving skills! Algorithms and data structures" I tried to rewrite the posted code in Python! -table of contents-
"Book to train programming skills to fight in the world" Python code answer example --1.3 URLify
"Book to train programming skills to fight in the world" Python code answer example --2.6 palindrome
"Book to train programming skills to fight in the world" Python code answer example --2.4 Splitting the list
"Book to train programming skills to fight in the world" Python code answer example --2.7 intersecting nodes
"A book to train programming skills to fight in the world" Python code answer example --1.8 "0" matrix
"A book to train programming skills to fight in the world" Python code Solution example --1.6 String compression
"A book to train programming skills to fight in the world" Python code answer example --3.1 Three stacks
"A book to train programming skills to fight in the world" Python code Solution example --1.7 Matrix rotation
"Book to train programming skills to fight in the world" Python code answer example --1.4 Permutation of sentences
"A book to train programming skills to fight in the world" Python code Solution example --2.8 Loop detection
"Book to train programming skills to fight in the world" Python code solution example --- Removed elements between 2.3
"Book to train programming skills to fight in the world" Python code Solution example --2.1 Remove duplicate elements
"A book to train programming skills to fight in the world" Python code answer example --1.9 Rotation of strings
"A book to train programming skills to fight in the world" Python code answer example --1.1 Duplicate character string
"A book to train programming skills to fight in the world" Python code answer example --2.2 Returns the Kth from the back
"A book to train programming skills to fight in the world" Python code answer example --1.2 Count the number of the same characters
I felt that I ported the Python code to C ++ 98.
"A book to train programming skills to fight in the world" Python code Solution example --2.5 The sum of two numbers shown in the list
Solve the spiral book (algorithm and data structure) with python!
Build a Python environment and transfer data to the server
I want to know the features of Python and pip
I tried to enumerate the differences between java and python
I want to map the EDINET code and securities number
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part1-
I tried to solve the ant book beginner's edition with python
[Introduction to Python] I compared the naming conventions of C # and Python.
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part2-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part4-
I wrote the code to write the code of Brainf * ck in python
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part3-
I tried to get and analyze the statistical data of the new corona with Python: Data of Johns Hopkins University
I tried to refactor the template code posted in "Getting images from Flickr API with Python" (Part 2)