AtCoder ABC377 復習(緑コーダーがPythonでA〜C問題まで)

ABC377 感想まとめ

トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377) - AtCoder

このところ出かけていたり、心身が不調だったりで2週ほどサボっていました。今回もリアルタイム参加はできなかったのですが、一応復習はしておこうということで、問題を解いてみました。

A - Rearranging ABC

入力文字列 S の中に、A B C が各1個ずつあれば、Yesになります。

S = input()
if S.count("A") == 1 and S.count("B") == 1 and S.count("C") == 1:
    print("Yes")
else:
    print("No")

B - Avoid Rook Attack

ちょっと解き方で悩みました。マスのサイズが8x8と少なめなので、64個の全マス(i,j)について、

• i行に#があるか
• j列に#があるか

を、そのつど調べるようにしました。

N = 8
S = []
for i in range(N):
    S.append(list(input()))

count = 0
for i in range(N):
    # i行に#があるか
    if S[i].count("#") > 0:
        continue
    
    # j列に#があるか
    for j in range(N):
        exist = False

        for k in range(N):
            if S[k][j] == "#":
                exist = True

        if exist == False:
            count += 1

print(count)

たぶん、"#"がある行/"#"がある列 を 配列とかsetとかで持っておいて、判定するほうが簡単にかけて処理回数も少ないと思います。。

C - Avoid Knight Attack

Bにつづいて、チェスのような問題。今回はマスの数が最大 10^9 四方なので、計算速度に気をつける必要があります。

この問題は、以下のような方針で解答しました。

• コマの動ける方向を moves として定義
• 各コマが置いてある座標を false_set に記憶していく
• 各コマが動ける座標を false_set に記録していく
• 「全マスの数(N * N) - false_set の数」 で最終的な答えが求まる

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

false_set = set() # 空でないマスの座標を記録

# コマが動ける座標
moves = [(-1, -2), (1, -2), (-2, -1), (2, -1), (-2, 1), (2, 1), (-1, 2), (1, 2)]

for i in range(M):
    a, b = map(int, input().split())
    # すでに置かれている
    false_set.add((a, b))

    # 8方向に移動できる。移動先はfalse_setに追加
    for move in moves:
        x = a + move[0]
        y = b + move[1]
        if 1 <= x <= N and 1 <= y <= N:
            false_set.add((x, y))

# 空のマスの数 = 全マスの数(N * N) - false_setの数
answer = N * N - len(false_set)
print(answer)

D - Many Segments 2

これは考えたのだけど、解答にはたどり着けず...。左端を固定すると良さそうだな、というのところまではわかったのですが...。

公式の解説動画を見て勉強しようと思います。

トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377) - YouTube