AtCoder ABC400 振り返り(緑コーダーがPythonでAB+CD問題)

AtCoder Beginner Contest 400 振り返り

今回はABの2問解答でした。Bまでは順調に解けたのですが、C問題で数式変形がうまくできずに正解が求まらず...。D問題は幅優先探索が正着なところを、深さ優先探索で解こうとして解けず...。

C, D問題はコンテスト終了後に、復習して解きました。

またしてもレーティングが減ってしまい、そろそろ緑陥落が見えてまいりました(あと−30)。

A - ABC400 Party

400 で割り切れるかを判定しています。

A = int(input())

if 400 % A == 0:
    print(400 // A) 
else:
    print(-1)

B - Sum of Geometric Series

数式通りに計算していきました。Pythonだとオーバーフローを考えていなくて良いのが楽ですね。

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

X = 0
for i in range(M+1):
    X += N ** i

    if X > 10 ** 9:
        print("inf")
        exit()

print(X)

C - 2^a b^2 (解説AC)

これは解説を見て解きました。

考え方としては...

• a は 1 から 60 までループさせれば良い
• b が偶数の場合、2 ^ a の項に統合してしまって良い
  • 2^2 * 6^2 → 2^4 * 3^2

なので、aをループさせて、そのa に対して条件を満たす B=1,3,5,7... の個数を求めれば良いということになる。

また、 他の方の解答を見ていて math.isqrt() を知りました。これだと平方根の整数部分だけが求められて、誤差が気にならなくなります。

N = int(input())

count = 0

for a in range(1, 61):
    A = 2 ** a
    if A > N:
        break

    B2 = N // A
    max_B = math.isqrt(B2)
    # 奇数だけカウント
    count += (max_B + 1) // 2

print(count)

D - Takahashi the Wall Breaker (解説AC)

壁を壊すパターンも含めて、幅優先探索を行えば良い。最短距離のものから処理したいので、通常は優先度付きキュー heapq を使用したいところですが、この問題では1問だけどうしてもTLEになってしまいます。

そこで、 01-BFS という手法を使うと良いとのことでした。これであれば deque を使えるので、より高速に処理することができます。

H, W = map(int, input().split())
S = [list("*" + input() + "*") for _ in range(H)]
S.insert(0, ["*"] * (W + 2))
S.append(["*"] * (W + 2))
A, B, C, D = map(int, input().split())

visited = [[INF] * (W + 2) for _ in range(H + 2)]
visited[A][B] = 0

# 幅優先探索
queue = deque()
queue.append((0, A, B))

while queue:
    break_count, x, y = queue.popleft()

    if x == C and y == D:
        break
    
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        # 通路を進むパターン
        if S[x + dx][y + dy] == ".":
            if visited[x + dx][y + dy] > break_count:
                visited[x + dx][y + dy] = break_count
                # 現状の最短距離なので、キューの左側に追加
                queue.appendleft((break_count, x + dx, y + dy))
                continue

        # 壁を壊すパターン
        if S[x + dx][y + dy] == "#":
            # 1個目の壁
            if visited[x + dx][y + dy] > break_count + 1:
                visited[x + dx][y + dy] = break_count + 1
                # 壁を壊したので、キューの右側に追加
                queue.append((break_count + 1, x + dx, y + dy))

            # 2個目の壁を壊せれば壊す
            if 0 < x + dx*2 < W + 1 and 0 < y + dy*2 < H + 1:
                if S[x + dx*2][y + dy*2] == "#" or S[x + dx*2][y + dy*2] == ".":
                    if visited[x + dx*2][y + dy*2] > break_count + 1:
                        visited[x + dx*2][y + dy*2] = break_count + 1
                        # 壁を壊したので、キューの右側に追加
                        queue.append((break_count + 1, x + dx*2, y + dy*2))

print(visited[C][D])