AtCoder version! Ant book (beginner) will be solved in detail with Python.
【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)
__ [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))
__ [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))
__ [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)
__ [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))
__ 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
__ [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)
__ [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)
__ [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.
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")
__ [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)
__ [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))
__ [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]))
__ [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