[GO] 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
【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)
__ [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).
【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).
【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
__ [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 __
- Divide the problem into multiple subproblems
- Evaluate the solution for each subproblem (there are multiple possible solution patterns for each subproblem)
- 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
__ [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.
-
- If the letter S'matches "?" Or SS → As it is
- When the character of S'is not "?" And the character of SS is "?" → Convert SS "?" To S'character
-
- 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
__ [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