AtCoder ABC391 振り返り感想戦(緑コーダーがPythonでABCD問題)

ABC 391感想まとめ

AtCoder Beginner Contest 391 - AtCoder

ABCD 4問解答でした。

A問題・C問題でちょっと時間を使ってしまい、D問題を解いた時点でもう残り時間がほぼなくなってしまったような印象でした。

A - Lucky Direction

反対方角のペアを作っておいて、ペアの一方があれば、もう一方を出力する作戦にしました。

D = input()
DIR = [("N", "S"), ("E", "W"), ("NE", "SW"), ("NW", "SE")]

for i in range(4):
    if D == DIR[i][0]:
        print(DIR[i][1])
        exit()
    if D == DIR[i][1]:
        print(DIR[i][0])
        exit()

節分の恵方巻にちなんだ問題ですかね

B - Seek Grid

地道にSとTを一文字ずつ比較します。

N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]
T = [list(input()) for _ in range(M)]

# Sの左上から総当たりでTと比較する
for i in range(N - M + 1):
    for j in range(N - M + 1):
        # Tと一致するかチェック
        error = False
        for k in range(M):
            for l in range(M):
                if S[i + k][j + l] != T[k][l]:
                    error = True
                    break
            if error:
                break
        if not error:
            print(i+1, j+1)
            exit()

C - Pigeonhole Query

Query 2 のときにその都度全探索で2羽以上入っている巣箱を求めると、計算量が多くなってしまう。
そのため、Query 1 を行うときに「移動元が 2羽→1羽 になった」「移動先が 1羽→2羽 になった」を求めておいて、計算量をへらしました。

N, Q = map(int, input().split())

counter2 = 0 # 2羽以上入っている巣箱の数
homes = [] # 巣箱の配列
positions = [0] * (N + 1) # 鳩がどこにいるかを記憶しておく配列

# 巣箱に入っている鳩の番号は set で管理
for i in range(0, N + 1):
    homes.append(set([i]))
    positions[i] = i

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        P, H = query[1], query[2]
        # 移動元の巣箱の情報を記憶
        previous_home = positions[P]
        prrevious_count = len(homes[previous_home])

        # 移動元の巣箱から削除し、移動先の巣箱に追加
        homes[previous_home].discard(P)
        homes[H].add(P)

        # 鳩の位置を更新
        positions[P] = H

        if prrevious_count > 1 and len(homes[previous_home]) == 1:
            # 移動元の巣箱が 2羽→1羽 になったときは、カウントを-1
            counter2 -= 1
        if len(homes[H]) == 2:
            # 移動先の巣箱が 1羽→2羽 になったときは、カウントを+1
            counter2 += 1

    else:
        # 2羽以上入っている巣箱の数
        print(counter2)

問題はたぶん 鳩の巣原理 - Wikipedia から考えたのかも。

D - Gravity

テトリスみたいな落ち物パズルゲーム風問題。

シミュレーションを行って、各ブロックが削除される時間を先に求めてしまうようにしました。

列ごとにブロックを deque で管理します。
「次に行が削除される時間 == 各列の deque の先頭の中で、最もY座標が上のブロックが落ちてきたとき」と考えて、削除される時間を求めます。

ループが多いので計算量が若干不安でしたが、うまく通ってくれました。

N, W = map(int, input().split())

# 各列について、ブロックをQueueで管理
cols = []
for i in range(W):
    cols.append(deque())

# 各列について、ブロックを追加
for i in range(N):
    box_num = i + 1
    X, Y = map(int, input().split())
    cols[X-1].append((Y, box_num))

deleted_times = [-1] * (N + 1) # 箱を削除した時間
can_delete = True # ブロックを削除できるか？判定

while can_delete:
    # 待ち時間の最大値=ブロックのY座標の最大値を求める
    max_Y = 0
    for j in range(W):
        #  列にブロックがない場合は削除できない
        if len(cols[j]) == 0:
            can_delete = False
            break
        Y, box_num = cols[j][0]
        max_Y = max(max_Y, Y)

    if not can_delete:
        break

    # 先頭を削除
    for j in range(W):
        Y, box_num = cols[j].popleft()

        # ブロックを削除した時間を記録
        deleted_times[box_num] = max_Y

# クエリに対してYes/Noを出力
Q = int(input())
for i in range(Q):
    t, a = map(int, input().split())
    deleted_time = deleted_times[a]
    if deleted_time == -1 or t < deleted_time:
        print("Yes")
    else:
        print("No")