Solve "AtCoder version! Ant book (beginner)" with Python!

AtCoder version! Ant book (beginner) will be solved in detail with Python.

1 All basics "Full search"

1-1 bit full search

ABC 045 C-Many formulas

image.png

【answer】

S = list(input())

ans = 0
for i in range(2**(len(S)-1)):
    plus = [""]*(len(S))
    fomula = ""
    for j in range(len(S)-1):
        if(i>>j & 1):
            plus[j] = "+"
    
    for i in range(len(S)):
        fomula += S[i] + plus[i]
    ans += eval(fomula)
    
print(ans)

ABC 104 C - All Green image.png image.png

__ [Explanation] __ Search all bits for not taking bonuses. Take a bonus and choose the remaining missing points from the one with the highest score.

【answer】

D,G = map(int,input().split())
l = list(list(map(int, input().split())) for _ in range(D))

#Sort in descending order of score
l = l[::-1]

ans = float("inf")
for i in range(2**D):
    total = 0
    cnt = 0
    for j in range(D):
        if (i>>j)&1:
            total += 100*(D-j)*l[j][0] + l[j][1]
            cnt += l[j][0]
    if total >= G:
        ans = min(ans,cnt)
        continue
    for j in range(D):
        if (i>>j)&1 == False:
            for k in range(l[j][0]):
                total += 100*(D-j)
                cnt+=1
                if total >= G:
                    ans = min(ans,cnt)
                    break
            break

print(ans)

1-2 DFS (depth-first search)

ATC 001 A Depth-first search

__ [Explanation] __ DFS (depth-first search) is an image of searching all the way to the back, and when there is nothing to search, return to the place where you have not searched and search again. Implement using Stack, which is LIFO (Last-In First-Out). image.png

【answer】

from collections import deque

def dfs(maze, sh, sw):
    #Initialize the reached list
    visited = [[0]*W for _ in range(H)]

    stack = deque([[sh,sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.pop()
        if maze[h][w] == "g":
            return("Yes")
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_h, new_w = h+i, w+j
            if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w])
    return("No")

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

#Find the starting position
for i in range(H):
    if maze[i].find("s") != -1:
        sh = i
        sw = maze[i].find("s")
        
print(dfs(maze, sh, sw))

1-3 BFS (breadth-first search)

ABC 007 C breadth-first search

__ [Explanation] __ BFS (breadth-first search) is an image of searching from shallow to shallow. Implement using Queue which is FIFO (First-In First-Out). image.png

【answer】

from collections import deque

def dfs(maze, sh, sw, gh ,gw):
    #Initialize the reached list
    visited = [[-1]*W for _ in range(H)]

    stack = deque([[sh,sw]])
    visited[sh][sw] = 0
    while stack:
        h, w = stack.popleft()
        if h == gh and w == gw :
            return(visited[h][w])
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_h, new_w = h+i, w+j
            if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    return("No")

H,W = map(int,input().split())
sh,sw = map(int, input().split())
gh,gw = map(int, input().split())
maze = [input() for _ in range(H)]

print(dfs(maze, sh-1, sw-1, gh-1, gw-1))

1-4 List of special conditions

ABC 054 C One-stroke Path

__ [Explanation] __ Use permutations to enumerate all the ways to connect graphs. Judge whether they are connected correctly and count them.

【answer】

from itertools import permutations

N,M = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(M)]

graph = [[False]*(N+1) for _ in range(N+1)]
for i in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

cnt = 0

for i in permutations(range(1,N+1)):
    #Consider starting point from 1
    if i[0] != 1:
        continue
    isJoin = True
    for j in range(1,N):
        if not graph[i[j-1]][i[j]]:
            isJoin = False
            break
    if isJoin:
        cnt += 1

print(cnt)

JOI 2009 Qualifying D Card Arrangement

__ [Explanation] __ Use permutations to enumerate the arrangement of integers. Create a sorted integer using map and join, add it to dic, and finally answer the number of integers in dic.

【answer】

from itertools import permutations

N = int(input())
S = int(input())
l = [int(input()) for _ in range(N)]
dic = {}
for i in permutations(l,S):
    i = map(str,i)
    dic[("".join(i))] = 1

print(len(dic))

2 Insane rush! "Greedy algorithm"

__ What is greedy algorithm __

  1. Divide the problem into multiple subproblems
  2. Evaluate the solution for each subproblem (there are multiple possible solution patterns for each subproblem)
  3. Evaluate the solution of the next subproblem (which can also be considered in multiple ways), with the one with the best evaluation as the solution of that subproblem (= local optimal solution).

Quote: I tried to solve a simple greedy algorithm

2-1 Coin problem

JOI 2007 Qualifying A Change

__ [Explanation] __ Count the number of coins from the largest coin.

【answer】

N = int(input())

N = 1000 - N
cnt = 0

l = [500,100,50,10,5,1]

for i in l:
    cnt += N // i
    N = N - i*(N//i)

print(cnt)

2-2 Section scheduling problem

KEYENCE Programming Contest 2020 B --Robot Arms

__ [Explanation] __ First, sort by the position of the right end of the robot arm. Look at the rightmost position in the order on the left, and exclude if they overlap. If they do not overlap, update the rightmost position.

【answer】

N = int(input())
l = [list(map(int,input().split())) for _ in range(N)]

ans = N
for i in l:
    x = 0 if i[0]-i[1] < 0 else i[0]-i[1]
    i[1] = i[0]+i[1]
    i[0] = x
    
l.sort(key=lambda x:x[1])

right = 0
for i in range(N):
    if right > l[i][0]:
        ans-=1
    else:
        right = l[i][1]

print(ans)

2-3 Greedy for the smallest dictionary order

ABC 076 C Dubious Document 2

__ [Explanation] __ First of all, what is the T character string and the number of remaining characters? Prepare the list SS filled with.

coder??
?coder?
??coder

The list SS of the created characters and the given S'are compared character by character.

    1. If the letter S'matches "?" Or SS → As it is
  1. When the character of S'is not "?" And the character of SS is "?" → Convert SS "?" To S'character
    1. Otherwise → Character strings that cannot be created

After that, fill the "?" Remaining in the SS with "a" so that it is the smallest in the dictionary order. 【answer】

S = input()
T = input()

n = len(S)-len(T)+1
ans = []
for i in range(n):
    SS = list("?"*(i) + T + "?"*(n-i-1))
    flag = True
    for i in range(len(S)):
        if S[i]=="?" or S[i]==SS[i]:
            pass
        elif S[i]!="?" and SS[i]=="?":
            SS[i] = S[i]
        else:
            flag = False
    if flag:
        ans.append("".join(SS).replace("?","a"))

if ans:
    ans.sort()
    print(ans[0])
else:
    print("UNRESTORABLE")

2-4 Greedy taking a stricter place

ABC 083 C Multiple Gift

__ [Explanation] __ The smallest multiple that is larger than the previous number is doubled. Therefore, double it and check until it exceeds Y.

【answer】

X,Y = map(int,input().split())

cnt=0
while X<=Y:
    cnt+=1
    X = X*2

print(cnt)

ARC 006 C Stacking

__ [Explanation] __ Look at the weight of the box at the top from the front, and if you can put it on, put it on. If you can't put it on, repeat the comparison with the box at the top of the next mountain.

【answer】

N = int(input())
W = [int(input()) for _ in range(N)]

l=[float("inf")]
for w in W:
    flag=True
    for i in range(len(l)):
        if l[i]>=w:
            l[i] = w
            flag=False
            break
    if flag:
        l.append(w)
        
print(len(l))

3 Remember and reuse "Dynamic programming"

3-1 01 Knapsack problem

AOJ Course 0-1 Knapsack Problem

__ [Explanation] __ dp [i] [j] ・ ・ ・ means the optimum solution up to the weight j using the luggage up to the i-th. ・ When w [i]> j This baggage cannot be put in, so update with the optimal solution for the previous baggage.

・ When w [i] ≤ j Think about when to put the i-th baggage. Since the weight w [i] increases, the value v [i] is added to the optimal solution of the weight of j-w [i] up to the i-1st. After that, take max when you do not put the i-th baggage.

Quote: Tsubasa's memorandum Dynamic programming (about the knapsack problem) There is a figure and it is very easy to understand.

【answer】

N,W = map(int,input().split())

v = [0] * N
w = [0] * N
for i in range(N):
    v[i],w[i] = map(int,input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

TDPC A Contest

__ [Explanation] __ Subset sum problem.

When checking if an input can be 3 to 5 If 2 in 5-3 is True, you can set it to 5! I will search with the feeling.

Flow of data dp at the time of input list [2,3]. dp[1][2] = dp[0][2-2] = dp[0][0] = True dp[2][3] = dp[1][3-3] = dp[1][0] = True dp[2][5] = dp[1][5-3] = dp[1][2] = True [0,2,3,5] becomes True.

【answer】

N = int(input())
l = list(map(int,input().split()))

_sum = sum(l)
dp = [[False]*(_sum+1) for _ in range(N+1)]
dp[0][0] = True

for i in range(1,N+1):
    for j in range(_sum+1):
        if l[i-1]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j] or dp[i-1][j-l[i-1]]

print(sum(dp[N]))

Recommended Posts

Solve "AtCoder version! Ant book (beginner)" with Python!
Solve AtCoder 167 with python
Solve AtCoder ABC166 with python
Solve AtCoder ABC 186 with Python
Solve AtCoder Problems Recommendation with python (20200517-0523)
Ant book with python (chapter3 intermediate edition ~)
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
I tried to solve the ant book beginner's edition with python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Solve Sudoku with Python
Solve AtCoder Beginner Contest 170 D --Not Divisible (ABC170D) with python (Eratosthenes sieve)
Solve AtCoder Beginner Contest 100-102
Solve POJ 2386 with python
Check version with python
Try to solve the programming challenge book with python3
[Python] Solve equations with sympy
Light blue with AtCoder @Python
Specify python version with virtualenv
Web scraping beginner with python
Atcoder Beginner Contest 152 Kiroku (python)
Solve AtCoder Beginner Contest159 D --Banned K (ABC159D) with python (count is too slow!)
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solve the spiral book (algorithm and data structure) with python!
solver> Link> Solve Excel Solver with python
Solve ABC163 A ~ C with Python
Solve ABC166 A ~ D with Python
Solve Atcoder ABC169 A-D in Python
Let's play with Excel with Python [Beginner]
Solve ABC168 A ~ C with Python
[Beginner] Extract character strings with Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Manage each Python version with Homebrew
Solve ABC158 A ~ C with Python
Ant book in python: Sec. 2-5 Graph
AtCoder Beginner Contest 174 C Problem (Python)
[Python Windows] pip install with Python version
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Ant book in python: page 42 coin problem
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Ant book in python: Priority queue self-implementation
Ant book in python: Sec. 2-4, data structures
Ant book in python: Sec.2-5 Dijkstra's algorithm
atCoder 173 Python
I wanted to solve ABC160 with Python
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
Ant book in python: page 43 Interval scheduling
order_by ('-created_at') ← What is "ー"? ?? ?? [Beginner learns python with a reference book]
Ant book in python: Sec. 2-5 Graph (preparation)
[Python] Solve 10 past elite problems of Atcoder
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
AtCoder Green tried to solve with Go
Solve Lake Counting (POJ NO.2386) with Python3
Ant book in python: page 49 Fence Repair
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Python hand play (let's get started with AtCoder?)
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
Let's solve simultaneous linear equations with Python sympy!
I wanted to solve NOMURA Contest 2020 with Python