iTranslated by AI
AtCoder ABC391 Editorial (Python)
This is an explanation of ABC391 (held on 2025/02/01) by a Python green-rated coder!
(I'm sorry, my variable naming was a bit too messy this time.)
Problem A
Writing 8 if statements might have worked, but I used a list instead.
Since we can pair directions like N→S and S→N, I placed the pairs next to each other and output the adjacent direction depending on whether the current direction is at an even or odd index.
D = input()
hougaku = ["N", "S", "E", "W", "NE", "SW", "NW", "SE"]
# If the input direction is at an even index, the one to the right; if odd, the one to the left
if hougaku.index(D) % 2 == 0:
print(hougaku[hougaku.index(D) + 1])
else:
print(hougaku[hougaku.index(D) - 1])
Problem B
Determine the top-left position of T and use loops to check if it matches.
For example, when N=10 and M=3, the top-left can be placed from the 0th to the 7th position, so the end value for range becomes N - M + 1 (=8). Be careful with the range.
Also, since the problem states there is exactly one answer, I use exit() to terminate immediately once it's found.
N, M = [int(x) for x in input().split()]
S = []
for _ in range(N):
S.append(list(input()))
T = []
for _ in range(M):
T.append(list(input()))
# Determine the starting position
for i in range(N - M + 1):
for j in range(N - M + 1):
ok = True
for di in range(M):
for dj in range(M):
if S[i + di][j + dj] != T[di][dj]:
ok = False
if ok:
print(i + 1, j + 1)
exit()
Problem C
I keep track of "which pigeons are in which box" using a list of sets.
By subtracting 1 from the answer when a pigeon leaves a box and that box ends up with exactly 1 pigeon, and adding 1 when a pigeon enters a box and it starts having multiple pigeons, you can answer the queries in O(1).
Also, searching for "which box a pigeon is in" every time will result in a timeout, so I store that in a list as well.
By the way, query inputs appear in this problem. I think it's simple to store the split values in a list like query and identify the type using query[0].
N, Q = [int(x) for x in input().split()]
box = [set([i]) for i in range(N)]
hato = [i for i in range(N)]
ans = 0
for _ in range(Q):
query = [int(x) for x in input().split()]
if query[0] == 1:
move_hato, move_to = query[1] - 1, query[2] - 1
move_from = hato[move_hato]
# If leaving the box leaves exactly 1 pigeon, subtract 1 from the answer
if len(box[move_from]) == 2:
ans -= 1
# It's useful to remember how to use sets
box[move_from].remove(move_hato)
box[move_to].add(move_hato)
hato[move_hato] = move_to
# If arriving at the box makes it have 2 pigeons, add 1 to the answer
if len(box[move_to]) == 2:
ans += 1
elif query[0] == 2:
print(ans)
Problem D
Sort the blocks for each column and find the block that will fall next. Then, one row disappears at the maximum time of those blocks. In this way, I recorded when each block disappears.
This time, I used sortedcontainers. It seems that add and popping from the front can be done in O(logN). I referred to this article for details!
# !pip install sortedcontainers
from sortedcontainers import SortedList
N, W = [int(x) for x in input().split()]
grid = [SortedList() for _ in range(W)]
ans = [10 ** 9 + 1 for _ in range(N)]
for i in range(N):
x, y = [int(x) - 1 for x in input().split()]
grid[x].add((y, i))
# Note: skip if there's a column without any blocks initially!
if min([len(x) for x in grid]) >= 1:
before_ans = -1
for _ in range(N): # Effectively repeating indefinitely
next_delete = before_ans + 1
for x in grid:
next_delete = max(next_delete, x[0][0] + 1)
# Finish when a column has zero blocks to delete
end = False
for x in grid:
ans[x[0][1]] = next_delete
x.pop(0)
if len(x) == 0:
end = True
if end:
break
before_ans = next_delete
# Queries start from here
Q = int(input())
for _ in range(Q):
t, a = [int(x) for x in input().split()]
print("Yes" if ans[a - 1] > t else "No")
Problem E
While performing operations step-by-step, I record "what the next number will be" and "what is the minimum number of changes needed to reverse the result" (a form of DP).
Ultimately, only the minimum number of changes required to reverse the result remains, and that is the answer.
N = int(input())
A = [int(x) for x in list(input())]
gyakuten_changes = [1 for _ in range(3 ** N)]
for i in range(N):
next_A = []
next_gc = []
# Process in groups of three
for j in range(len(A) // 3):
piece = A[j * 3 : (j + 1) * 3]
gc_piece = gyakuten_changes[j * 3 : (j + 1) * 3]
if piece.count(0) > piece.count(1):
next_A.append(0)
else:
next_A.append(1)
# If all are the same color, take the sum of the two smallest (sum - max)
if abs(piece.count(0) - piece.count(1)) == 3:
next_gc.append(sum(gc_piece) - max(gc_piece))
# If there is one '1', remove the change count corresponding to that '1',
# and change the smaller of the two remaining '0's
elif piece.count(1) == 1:
del gc_piece[piece.index(1)]
next_gc.append(min(gc_piece))
# Similarly
elif piece.count(0) == 1:
del gc_piece[piece.index(0)]
next_gc.append(min(gc_piece))
else:
# This case should be unreachable; error handling for safety
raise RuntimeError
A = next_A
gyakuten_changes = next_gc
# Finally, only one remains. Incidentally, A[0] should also represent the final state.
print(gyakuten_changes[0])
Problem F & G (None)
I skipped these because I couldn't solve them.
Contest Results
taketii's results in AtCoder Beginner Contest 391: 1427th place
Performance: 1373 equivalent
Rating: 978→1027 (+49) :)
Updated Highest and reached 5th Kyu!
I'm glad I could achieve my previous declaration!!
Promotion
I always upload my solutions here after the contest ends. Please take a look if you'd like!
Discussion