AtCoder ABC387 振り返り感想戦(緑コーダーがPythonでA,B,D問題)

ABC 387感想まとめ

AtCoder Beginner Contest 387（Promotion of AtCoderJobs） - AtCoder

ABC387はABDの3問回答でした。

今回は何と言ってもC問題が難しかったようです。私もC問題は早々に諦めて、D問題に取り組みました。難易度的にも C >>> D だったようでした。

D問題に着手した判断が結果的には良かったようで、思った以上の成績が出せました。

C問題は桁DPを使って解くようなのですが、公式解説を見てもよくわからないので、今後の復習課題です。

そもそも、桁DPはそんなに自信がない...

A - Happy New Year 2025

問題に書いてあるとおり、(A+B)^2を計算すればokです。

A, B = map(int, input().split())
print((A+B)**2)

B - 9x9 Sum

これも問題に書いてあるとおり、九九の掛け算のうちでX以外の数を全部足せばokです。

X = int(input())

answer = 0
for i in range(1, 10):
    for j in range(1, 10):
        if i * j != X:
            answer += i * j
print(answer)

C - Snake Numbers [未回答]

これが今回の難問でした。私も結構悩んだのですが、どうにも解けず...。行き詰まってD問題を見てみたら「CよりDのほうが典型的なアルゴリズムで解けそう...」ということで、D問題に着手しました。

結果的に、これは好判断だったようです。

D - Snaky Walk

これは迷路の最低移動距離探索なので、幅優先探索で実装しました。

注意点は、水平方向移動→垂直方向移動→水平→垂直...と交互にしか移動できない制限です。

これは、queue に突っ込む tuple に (座標i, 座標j, 移動方向(水平or垂直)) と移動方向を含めることで対応しました。

該当のマスに 水平移動/垂直移動 どちらで来たかがわかれば、次に進める方向はどちらなのかがわかる仕組みです。

INF = 10 ** 18

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

# 地図の四方を # で囲む
S = []
S.append("#" * (W + 2))
for i in range(H):
    s = "#" + input() + "#"
    S.append(s)
S.append("#" * (W + 2))

# スタート地点を探す
START = (0,0)
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == "S":
            start = (i, j)
            break

# 水平方向の移動と垂直方向の移動
MOVES_H = [(0, 1), (0, -1)]
MOVES_V = [(1, 0), (-1, 0)]

# 水平・垂直方向移動時の、スタートからの距離
dist_h = [[INF] * (W + 2) for _ in range(H + 2)]
dist_v = [[INF] * (W + 2) for _ in range(H + 2)]

# スタート地点は移動距離0、
dist_h[start[0]][start[1]] = 0
dist_v[start[0]][start[1]] = 0


# 幅優先探索
que = deque()

# スタート地点には、水平方向と垂直方向両方入れとく
que.append((start[0], start[1], "V"))
que.append((start[0], start[1], "H"))

while que:
    i, j, direction = que.popleft()
    if direction == "H":
        # Hで来た場合(前のマスはV)
        for di, dj in MOVES_V:
            # 次はV方向に移動
            ni, nj = i + di, j + dj
            if S[ni][nj] == "#":
                continue
            if S[ni][nj] == "G":
                print(dist_v[i][j] + 1)
                exit()
            if dist_h[ni][nj] > dist_v[i][j] + 1:
                dist_h[ni][nj] = dist_v[i][j] + 1
                que.append((ni, nj, "V"))
    else:
        # Vで来た場合(前のマスはH)
        for di, dj in MOVES_H:
            # 次はH方向に移動
            ni, nj = i + di, j + dj
            if S[ni][nj] == "#":
                continue
            if S[ni][nj] == "G":
                print(dist_h[i][j] + 1)
                exit()
            if dist_v[ni][nj] > dist_h[i][j] + 1:
                dist_v[ni][nj] = dist_h[i][j] + 1
                que.append((ni, nj, "H"))

print(-1)