Zenn
🗂

[Python]AtCoder Beginner Contest 180個人的メモ[AtCoder]

2020/10/17に公開
Python
競技プログラミング
AtCoder
tech

ABC180

所感

abcde5完
1396パフォ
やったぜ

A - box

最初にNからAを引いたときにマイナスになる可能性があるが，ボールの個数が負になることはありえないので0にする必要がある
そこだけ注意
と思っていたが，制約を見るとそうはならないっぽい
コンテスト後まで気づかなかった
結果的には良かったが，読み間違えていたので今後は気を付けたい

#!/usr/bin/env python3
def main():
    N, A, B = map(int, input().split())

    N -= A
    if N < 0:
        N = 0
    print(N + B)


if __name__ == '__main__':
    main()

B - Various distances

それぞれを計算しつつ出力すればおｋ
すべて絶対値の計算なので，入力時に絶対値にしておく

#!/usr/bin/env python3
def main():
    _ = int(input())
    x = [abs(int(x)) for x in input().split()]

    print(sum(x))
    print(sum([a ** 2 for a in x]) ** 0.5)
    print(max(x))


if __name__ == '__main__':
    main()

C - Cream puff

約数の列挙
同じ約数が列挙される場合があるのでそこに注意
例えばN=4のとき列挙されるのは[1, 2, 2, 4]となって2が重複してる
それで1waした
出力は昇順で

#!/usr/bin/env python3
def main():
    N = int(input())

    ans = set()
    for denominator in range(1, int(N ** 0.5) + 1):
        if N % denominator == 0:
            ans.add(denominator)
            ans.add(N // denominator)

    ans = sorted(list(ans))
    for n in ans:
        print(n)


if __name__ == '__main__':
    main()

D - Takahashi Unevolved

X\times A < X + Bを満たす内はAを掛けて，満たさなくなったらBを足して行けば良い
Bを足していく操作は10^9以上になり得るのでシミュレーションはできない
なのでAを掛ける回数をNとすると，(Y-X*A^{N}) // Bを計算することでBを足す回数をO(1)で求められる
最後にX<Yを確実に満たす様にwhile文を入れた
最初のwhileループは最悪の場合でも2のべき乗だから，60回程で済むので計算量はおｋ

waしまくってすごい迷走してたので，少しおかしなコードになってる
最初のAを掛ける操作中にX>Yとなる場合に気づかず4waした
もったいない

#!/usr/bin/env python3
def main():
    X, Y, A, B = map(int, input().split())

    ans = 0
    while X * A <= X + B:
        if X >= Y:
            print(ans - 1)
            return
        ans += 1
        X *= A
    res = (Y - X) // B
    ans += res
    X += B * res
    while X >= Y:
        ans -= 1
        X -= B
    print(ans)


if __name__ == '__main__':
    main()

解説を基にした，もっと簡潔なコード

#!/usr/bin/env python3
def main():
    X, Y, A, B = map(int, input().split())

    ans = 0
    while X * A <= X + B and X * A < Y:
        ans += 1
        X *= A
    print(ans + (Y - 1 - X) // B)


if __name__ == '__main__':
    main()

E - Traveling Salesman among Aerial Cities

良く分かんなかったけど問題名見て蟻本の巡回セールスマン問題のコードをパクって，少し変えたらacしちゃった
bitDPとかいうやつらしい

#!/usr/bin/env python3
def main():
    N = int(input())
    citys = [list(map(int, input().split())) for _ in range(N)]
    INF = 10 ** 18

    dp = [[INF] * N for _ in range(1 << N)]
    dp[(1 << N) - 1][0] = 0

    for s in range((1 << N) - 2, -1, -1):
        for v in range(N):
            for u in range(N):
                if not s >> u & 1:
                    a, b, c = citys[v]
                    p, q, r = citys[u]
                    length = abs(p - a) + abs(q - b) + max(0, r - c)
                    dp[s][v] = min(dp[s][v], dp[s | 1 << u][u] + length)
    print(dp[0][0])


if __name__ == '__main__':
    main()

参考資料

Discussion