AtCoder ABC391解説(Python)
Python緑コーダーによる、ABC391（2025/02/01実施）の解説です！
（今回はなんか変数の命名が雑すぎでした、すみません）
A問題
実際にif文を8個書くのも良さそうですが、自分はリストを使いました。
N→S、S→Nのように、2つずつ互いにペアにすることができるので、
ペアを隣において、方角が偶数番目か奇数番目かによって隣の方角を出力する感じです。
D = input()
hougaku = ["N", "S", "E", "W", "NE", "SW", "NW", "SE"]
# 入力された方角が偶数番目なら1個右のもの、奇数番目なら1個左のもの
if hougaku.index(D) % 2 == 0:
print(hougaku[hougaku.index(D) + 1])
else:
print(hougaku[hougaku.index(D) - 1])
B問題
Tの左上の位置を決めて、ループで同じか判断します。
例として、N=10、M=3のときは、左上は0番目から7番目までにおけるので、
rangeの終了値はN - M + 1(=8) となります。範囲に注意しましょう。
また、条件より答えは1つだけなので、見つかったらexit()を行って即座に終了するようにしています。
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()))
# スタートの位置を決める
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()
C問題
「箱にどのハトがいるか」をsetのリストで持っておきます。
ハトが箱から去ってその箱が1羽になるときに答えを-1し、箱へ来て複数羽になるときに答えを+1しておくことで、クエリにO(1)で答えることができます。
また、「ハトがどの箱にいるか」を毎回検索すると時間切れになるので、それもリストで保管しておきます。
ちなみに、この問題ではクエリの入力が登場しますが、
値を区切ってqueryに保管して、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]
# 箱から去るときに1羽になるなら答えを-1
if len(box[move_from]) == 2:
ans -= 1
# Setの使い方は覚えておいた方が便利
box[move_from].remove(move_hato)
box[move_to].add(move_hato)
hato[move_hato] = move_to
# 箱に来るときに1羽になるなら答えを+1
if len(box[move_to]) == 2:
ans += 1
elif query[0] == 2:
print(ans)
D問題
各列ごとにブロックをsortして、次に落ちてくるブロックを探します。
すると、その時間の最大のところで1行消えます。
このように、各ブロックがいつ消えるかを記録していっています。
今回はsortedcontainersを使いました。
addや先頭のpopがO(logN)でできるそうです。
詳しくはこの記事を参考にしています！
# !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))
# はじめにブロックがない列があったら飛ばすように注意！
if min([len(x) for x in grid]) >= 1:
before_ans = -1
for _ in range(N): # ほぼ無限に繰り返す意味
next_delete = before_ans + 1
for x in grid:
next_delete = max(next_delete, x[0][0] + 1)
# 消せるブロックが0の列ができたら終わり
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
# ここからクエリ
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")
E問題
1回ずつ操作を行いながら、「次の数は何か」と「形勢逆転には最小で何個変えるか」を記録していきます。（一種のDP）
最後に形勢逆転の最小数が1個残るので、それが答えです。
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 = []
# それぞれの3つずつ見ていく
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)
# 全て同じ色の時は、小さい順に2個（sum - max）
if abs(piece.count(0) - piece.count(1)) == 3:
next_gc.append(sum(gc_piece) - max(gc_piece))
# 1が1個の時は、1にあたる変化数を消して、
# あと2個の0の中で小さい方を変えればOK
elif piece.count(1) == 1:
del gc_piece[piece.index(1)]
next_gc.append(min(gc_piece))
# 同様
elif piece.count(0) == 1:
del gc_piece[piece.index(0)]
next_gc.append(min(gc_piece))
else:
# これ以外はありえないので、なんか変な時のエラー
raise RuntimeError
A = next_A
gyakuten_changes = next_gc
# 最後に1個だけ残る、ちなみにA[0]も最後の形勢になってるはず
print(gyakuten_changes[0])
F問題・G問題（なし）
解けなかったのでスキップです。
コンテスト結果
taketiiさんのAtCoder Beginner Contest 391での成績：1427位
パフォーマンス：1373相当
レーティング：978→1027 (+49) :)
Highestを更新し、5 級になりました！
前回の宣言が達成できてよかった！！
宣伝
コンテスト終了後、いつもここに解答をアップロードしています。
良ければ見てみてください！
Discussion