AtCoder ABC405 振り返り(緑コーダーがPythonでABCD問題)

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY） - AtCoder

ちょっと最近、集中力が切れがちなので慎重にunrated参加です（実際コンテスト中に20分ほど離席してしまった）。結果はABCDの4問解答(B問題で1ペナ)でした。

A - Is it rated?

素直に場合分けして解きました。if文はもっと短くかけますが、ミスがないようにこのくらいでいいかなと...。

R, X = map(int, input().split())
if X == 1:
    if 1600 <= R <= 2999:
        print("Yes")
    else:
        print("No")
else:
    if 1200 <= R <= 2399:
        print("Yes")
    else:
        print("No")

B - Not All

ちょっと時間がかかってしまった上に、1ペナでした。

考え方は以下のようにしました。

• 1 数字の出現回数を記録する配列 counter[] を用意する
• 2 配列 A の末尾の値の、カウントを減らす
• 3 counter[] が全て1以上かチェック
• 2,3 を繰り返し

より単純に、配列Aの末尾を短くする → 配列A内の数字をカウント としても、計算量は十分間にあるので、そちらのほうが良かったかもしれません。

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

# 数字の出現回数を記録する配列
counter = [0] * (M+1)
for i in range(len(A)):
    value = A[i]
    counter[value] += 1

# 各数字が1個以上あるかを判定する
def check():
    for i in range(1, len(counter)):
        if counter[i] <= 0:
            return False
    return True

# 初期状態で各数字が1個以上あるかを判定する
if check() == False:
    print(0)
    exit()

# A[]の末尾から数字カウントを減らしていく
for i in range(1, len(A) + 1):
    value = A[-1 * (i)]
    counter[value] -= 1

    if check() == False:
        print(i)
        exit()

C - Sum of Product

# N = 4の場合
answer = A1*A2 + A1*A3 + A1*A4 + A2*A3 + A2*A4 + A3*A4
↓
answer = (A1 + A2 + A3) * A4
+ (A1 + A2) * A3
+ (A1) * A2

上のように式変形をすると、(A[1]からA[k-1]までの累積和) * A[k] を使うと、効率よく計算できる事がわかります。

N = int(input())
A = list(map(int, input().split()))

# Aの累積和を求める
sum_a = []
sum_a.append(0)
for i in range(len(A)):
    next = sum_a[-1] + A[i]
    sum_a.append(next)

# 累積和を使って、答えを求める
answer = 0
for i in range(2, N+1):
    answer += sum_a[i-1] * A[i-1]

print(answer)

D - Escape Route

問題文とは逆に、出口'E'からスタートして、各通路'.'に最短距離でどうやって到達するか...を考えました。

最短距離は幅優先探索で求められますので、そのようにしました。

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

# 地図の周囲を"#"で囲うと、マップ外判定が楽になる
S = []
S.append(list("#" * (W + 2)))
for i in range(H):
    S.append(list("#" + input() + "#"))
S.append(list("#" * (W + 2)))

# 答えの書き込み用に、SをコピーしてTを作成
T = []
for i in range(len(S)):
    line = S[i].copy()
    T.append(line)

# 出口 E の座標を求めておく
e_list = []
for y in range(len(S)):
    for x in range(W + 2):
        if S[y][x] == "E":
            e_list.append((x, y))

# 幅優先探索
que = deque()

# スタート地点をキューに入れる
for i in range(len(e_list)):
    x, y = e_list[i]
    dist = 0
    que.append((dist, x, y))

# 移動できる方向(上下左右)と、マス目にいれる記号の配列
next_dir = [(1,0,"<"), (-1,0,">"), (0,1,"^"), (0,-1,"v")]

# 幅優先探索
while que:
    dist, x, y = que.popleft()

    # 行ける通路があれば、キューに入れる
    for dx, dy, char in next_dir:
        if T[y+dy][x+dx] == ".":
            T[y+dy][x+dx] = char
            que.append((dist+1, x+dx, y+dy))

for i in range(1, H+1):
    line = T[i]
    line = line[1:-1]
    print("".join(line))