AtCoder ABC 176 Python (A ~ E)
Summary
A, B, C solved. I think D and E can be solved in a little more time, but I couldn't solve them at the time of the contest, and it became AC at a later date.
problem
https://atcoder.jp/contests/abc176
A. Takoyaki
Answer
N, X, T = map(int, input().split())
if N % X == 0:
ans = (N // X) * T
else:
ans = (N // X) * T + T
print(ans)
Cases were divided according to whether the number N of takoyaki to be made is a multiple of X, which is the maximum capacity of the takoyaki machine.
B. Multiple of 9
Answer
N = list(str(input()))
total = 0
for i in range(len(N)):
total += int(N[i])
if total % 9 == 0:
print('Yes')
else:
print('No')
To the problem statement
"The integer N is a multiple of 9, and the sum of the numbers in each digit when N is expressed in decimal is an equivalence."
Since he wrote a hint, I will drop it in the code as it is. Didn't you need this hint? I thought.
C. Step
Answer
N = int(input())
A = list(map(int, input().split()))
total = 0
for i in range(N-1):
if A[i] > A[i+1]:
diff = A[i] - A[i+1]
total += diff
A[i+1] += diff
print(total)
Compare the current A [i] with the next A [i + 1], and if A [i + 1] is larger, add the difference.
It was easy for C problem, so I was worried that there might be some pitfalls before submitting, and I thought that there might be something because the maximum value of A, which is a constraint, is as large as 10 ** 9. I tried to put it out for the time being and it passed.
D. Wizard in Maze
Answer (I will pass it with AC pypy at a later date. Python is TLE)
#---------------------------------[import]---------------------------------#
from collections import deque
#---------------------------------[Input reception / initial setting]---------------------------------#
H, W = map(int, input().split())
C = tuple(map(int, input().split())) #Magic position
D = tuple(map(int, input().split())) #goal
D_y = D[0] -1 #0 start
D_x = D[1] -1 #0 start
S = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[C[0]-1][C[1]-1] = 0 #initial value
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Ordinary movement
main_q = deque()
magic_q = deque() #Queue for magic
main_q.append((C[0]-1, C[1]-1))
#---------------------------------[BFS]---------------------------------#
while main_q:
y, x = main_q.popleft()
magic_q.append((y, x))
for move in moves:
dy, dx = move
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
continue
if S[moved_y][moved_x] == '#':
continue
if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
main_q.append((moved_y, moved_x))
visited[moved_y][moved_x] = visited[y][x]
#---------------------------------[BFS for magic]---------------------------------#
if not main_q: # main_If q is empty, use magic from searched
while magic_q:
y, x = magic_q.popleft()
for dy in range(-2, 3):
for dx in range(-2, 3):
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
continue
if S[moved_y][moved_x] == '#':
continue
if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
main_q.append((moved_y, moved_x))
visited[moved_y][moved_x] = visited[y][x] + 1
#---------------------------------[Answer display]---------------------------------#
answer = visited[D_y][D_x]
print(answer)
The moment I read the problem, I thought I couldn't solve it with BFS, but I couldn't solve it at the time of the contest because I couldn't implement it well using magic.
The policy is
- First, move normally with move A (Implement the first BFS here)
- After performing all movement A, try movement B with magic from the place searched by movement A (stored in `` `magic_q```) (Implement the second BFS here)
- Start moving again with move A from the location searched with move B (stored in
main_q) - Repeat steps 1 to 3 below. When moving, record the number of times Magic has been used in `` `visited```
- The number of times recorded in the destination `` `visited``` is the answer It will be.
Assuming that you can write ordinary BFS, I think the key to this problem was whether or not you could implement "record the number of times Magic was used in visited```.
With the above code, it becomes TLE in python and you need to pass it with pypy. I think that python will work if you devise it, but I have not improved it because the code as it is is easier for me to understand.
E. Bomber
Answer (AC at a later date)
import numpy as np
H, W, M = map(int, input().split())
row = np.zeros(W)
col = np.zeros(H)
memo = []
for _ in range(M):
h, w = map(int, input().split())
h -=1
w -=1
row[w] += 1
col[h] += 1
memo.append((h, w))
col_max = col.max()
row_max = row.max()
max_col_indexes = np.where(col == col_max)[0]
max_row_indexes = np.where(row == row_max)[0]
ans = col_max + row_max -1
memo = set(memo)
for c in max_col_indexes:
for r in max_row_indexes:
if (c, r) not in memo:
ans = col_max + row_max
print(int(ans))
exit()
print(int(ans))
The policy was decided immediately and I applied the code, but I couldn't reduce the amount of calculation and couldn't AC at the time of the contest.
As a policy
- Count the bombs that exist in each row and column, and get the maximum number of bombs (row max, column max) for each row and column, and the row number and column number that will be max.
- If you are counting bombs with the same row and column numbers, then `` `row max + column max -1``` is the answer.
- If you are not counting bombs with the same row and column numbers that are max, then `` `row max + column max``` is the answer
- To determine if the same bomb is counted in the row and column, check if there is a bomb at the coordinates of the max row number and column number. is.
If you don't put ``` memo = set (memo)` `` in the code, it will be TLE.
Recommended Posts