Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "005 --- 009 All Search: All Enumeration to Reduce the Number of Streets by Ingenuity".

2. Summary

[006. Sumitomo Mitsui Trust Bank Programming Contest 2019 D --Lucky PIN] was a little difficult. 007 and 009 can be difficult if you don't have a vector.

3. Main story

005 --009 All search: All enumeration to reduce the number of streets by devising

  1. AtCoder Beginner Contest 095 C - Half and Half image.png

Answer

A, B, C, X, Y = map(int, input().split())

answer_1 = A * X + B * Y #When buying all at A and B
answer_2 = C * 2 * max(X, Y) #If you buy everything in C

# answer_3:A first,When buying B and then supplementing the rest with C
# answer_4:Buy C first and then the rest A,When supplementing with B
if X > Y:
    answer_3 = A * Y + B * Y + C * (X - Y) * 2
    answer_4 = A * (X - Y) + C * Y * 2
else:
    answer_3 = A * X + B * X + C * (Y - X) * 2
    answer_4 = B * (Y - X) + C * X * 2

answer = min(answer_1, answer_2, answer_3, answer_4)
print(answer)

To buy at the cheapest price, it is enough to try the following 4 ways.

  1. When buying all at A and B
  2. If you buy everything in C
  3. When buying up to a small quantity of A and B first and then supplementing the rest with C
  4. When buying a small quantity with C first and then supplementing the rest with A and B

The answer is to find the minimum value after calculating these four amounts.


006. Sumitomo Mitsui Trust Bank Programming Contest 2019 D --Lucky PIN

image.png

Answer

import itertools

def find_index(l, x): #In the built-in function index, if it is not found, an error will occur.-Fixed to return 1
    if x in l:
        return l.index(x)
    else:
        return -1


if __name__ == "__main__":
        
    N = int(input())
    S = [int(c) for c in input()]
    table = list(range(10))

    count = 0
    for p in itertools.product(table, repeat=3): #Allow duplication 1~Arrange three numbers of 9
        target = list(p)

        s1_index = find_index(S, target[0])
        if s1_index == -1:
            continue
        s1 = S[s1_index+1:]

        s2_index = find_index(s1, target[1])
        if s2_index == -1:
            continue
        s2 = s1[s2_index+1:]
        
        s3_index = find_index(s2, target[2])
        if s3_index == -1:
            continue
        
        count += 1

    print(count)

This answer is not good.

If you mainly search for the character string S, the maximum length of S is 30,000, and if you try all the methods to select three from here, it will be on the order of about 10 ** 12, so I will think of a different method.

If you think about how to select three numbers from 0 to 9 by allowing duplicate numbers instead of the main character string S, it will be in the order of 10 ** 3, so I feel like I can go if I think mainly about this.

The policy is

  1. Enumerate 3-digit numbers using 0-9 in itertools.product
  2. Find out the index number where the number in the left digit first appears in the string S
  3. Check the index number where the middle digit appears for the first time in the character string S after the index number found above.
  4. Check the index number where the number in the right digit appears for the first time in the character string S after the index number found above.
  5. If the index number is not found because it is 2 to 3, `` `break``` respectively

is.


007. JOI 2007 Final Selection 3-The Oldest Ruins

image.png

Answer


import itertools

n = int(input())
dots = [tuple(map(int, input().split())) for _ in range(n) ]
dots_set = set(dots)

#Think of an ABCD square
max_area = 0
for A, B in itertools.combinations(dots, 2):
    Ax, Ay = A
    Bx, By = B

    Cx, Cy = Bx - (By - Ay), By + (Bx - Ax) 
    Dx, Dy = Ax - (By - Ay), Ay + (Bx - Ax)
    
    if (Cx, Cy) in dots_set and (Dx, Dy) in dots_set:
        area = (Ax - Bx) ** 2 + (Ay - By) ** 2
        max_area = max(max_area, area)

print(max_area)

If 2 points are determined from the given coordinates, 4 points and area for creating the square will be determined. Therefore, as a policy, we will try all the methods of selecting two points from the coordinates and judge whether or not a square can be created.

  1. List how to select 2 points from coordinates with itertools (let's call them A and B)
  2. Find the remaining two points C and D when creating a square from two points
  3. Determine if C, D are given and included in the set of coordinates
  4. If included, find the area and record the maximum value

is. When determining whether points C and D are included in a given set of coordinates, the list in dots usually results in `TLE```, so ` Must be dots_set = set (dots) `` `.


  1. Square869120Contest #6 B - AtCoder Markets image.png

Answer

N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

min_time = float('inf')
for a in A:
    for b in B:
        total_time = 0
        for i in range(N):
            total_time += abs(a - A[i]) + abs(A[i] - B[i]) + abs(b - B[i])
        
        min_time = min(min_time, total_time)

print(min_time)

It seems best to place the entrance and exit in either the given Ai or Bi (probably there are other best places ...). So try all of A and B to find the one that will give you the least amount of time.


009. JOI 2008 Qualifying 4-Search for constellations

image.png image.png

Answer

m = int(input()) #m is the number of stars in the constellation you are looking for
target = [tuple(map(int, input().split())) for _ in range(m)] #Coordinates of the constellation you want to find
n = int(input()) #n is the number of stars in the photo
stars = [tuple(map(int, input().split())) for _ in range(n)] #Coordinates of stars on the photo
set_stars = set(stars)

target_vector = [] #Hold relative position as vector
for i in range(m-1):
    y1, x1 = target[i]
    y2, x2 = target[i+1]
    vector_y, vector_x = y2 - y1, x2 - x1
    target_vector.append((vector_y, vector_x))

#Add vectors for all stars.
target_y, target_x = 0, 0 
for star in stars:
    y, x = star
    new_y, new_x = y, x
    count = 0
    for vector in target_vector:
        y_vector, x_vector = vector

        new_y += y_vector
        new_x += x_vector

        if (new_y, new_x) not in set_stars:
            break

        count += 1
        if count == m - 1: #If there are stars after all vector addition, the starting coordinates are the source of the answer
            target_y, target_x = y, x 
            break
#The answer is the coordinates relative to the first coordinates of the target
answer_y = target_y - target[0][0]
answer_x = target_x - target[0][1]

print(answer_y, answer_x)

I did the subscripts y and x in the reverse of the problem setting, but there is an answer.

The policy is

  1. Hold the desired constellation shape as a vector `` `target_vector``` (counterclockwise)
  2. Move all the stars in the photo according to the vector and check if there are stars in the coordinates after the movement.
  3. If there is no star, break, if there is, count the number of vectors used, and if it can be used m-1``` times, the constellation is reproduced.
  4. If you can reproduce the constellation, take the difference between the coordinates that became the starting point and the first coordinates of the target constellation, and that is the answer.

is.

Recommended Posts

Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Extract images and tables from pdf with python to reduce the burden of reporting
python beginners tried to predict the number of criminals
I tried to get the number of days of the month holidays (Saturdays, Sundays, and holidays) with python
[Python] A program to find the number of apples and oranges that can be harvested
"The one that blocks all Twitter accounts in the database" created by beginners of Python learning day
I tried to solve the ant book beginner's edition with python
About bit full search that often appears in competition pros From the eyes of beginners with python
[Python] A program that calculates the number of socks to be paired
I tried to verify and analyze the acceleration of Python by Cython
Divides the character string by the specified number of characters. In Ruby and Python.
[Python] A program that calculates the number of updates of the highest and lowest records