AtCoder ABC475振り返り (PythonでABC問題)

ABC475を振り返ります

今回はABCまで3問解答でした。
B問題で答えの順番を間違えるうっかりミスをしてしまい、1ペナでした。
・1円,10円,100円の順番が正しいところを、逆さまにしてしまった
・順番だけでなく、他の箇所も間違っていたのでなんとも言えない...

D問題は素数判定問題で、エラトステネスの篩 が分かれば解けるの問題です。
しかし、事前に エラトステネスの篩 のライブラリを用意しておらず、その場で書いたら誤っていてWAでした。
(0と1を素数にしてしまっていた...というミス)

もったいなかったので、エラトステネスの篩を自前ライブラリに追加します...。

A - mnclr

入力文字の間に "o" を入れるようにしました。

S = list(input())

# 文字の間に "o" を追加する
answer = []
for i in range(len(S) - 1):
    answer.append(S[i])
    answer.append("o")

answer.append(S[-1])

ans = "".join(answer)
print(ans)

B - Change

1回の支払いごとに、お釣りの枚数を計算するようにしました。
意外と計算が面倒...。

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

# それぞれのお釣りの枚数
v100 = 0
v10 = 0
v1 = 0

for i in range(len(A)):
    price = A[i]

    # おつりが出ないとき
    if price % 1000 == 0:
        continue

    # 1000 円以下のお釣りを計算
    ret = 1000 - price % 1000

    v100 += ret // 100
    v10 += (ret % 100) // 10
    v1 += ret % 10

print(v1, v10, v100)

C - Walk the Line

一見グラフ問題（幅優先探索とか）っぽさもあるんですが、それだと計算が間に合わなさそうです。

実は、以下のパターンを全探索しても、計算は間に合いそうです。

1. スタート地点から左に行って折り返し戻ってきて、スタート地点から右に片道で進む
2. スタート地点から右に行って折り返し戻ってきて、スタート地点から左に片道で進む

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

# 距離計算用に、累積和を求めておく
sum_a = [0]
sum_a.append(A[0])
for i in range(1, len(A)):
    sum_a.append(sum_a[i] + A[i])

# 左右の移動範囲を全探索
answer = 1
for left in range(0, S):
    for right in range(S-1, len(sum_a)):
        # パターン1 = leftまで行って戻ってきて、rightまで進む
        dist = (sum_a[S-1] - sum_a[left]) * 2 + (sum_a[right] - sum_a[S-1])
        if dist <= L:
            answer = max(answer, right - left + 1)

        # パターン2 = rightまで行って戻ってきて、leftまで進む
        dist2 = sum_a[S-1] - sum_a[left]  + (sum_a[right] - sum_a[S-1]) * 2
        if dist2 <= L:
            answer = max(answer, right - left + 1)

print(answer)