AtCoder Beginner Contest 180の感想

ABC180をコンテスト後に解いた。

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – box

やるだけ。

n, a, b = map(int, input().split())
ans = n - a + b
print(ans)

B – Various distances

numpyやscipyに距離を求める関数があるけど、問題文に定義を書いてくれていたのでそのまま実装。

n = int(input())
x = list(map(int, input().split()))

manhattan = sum(map(abs, x))
print(manhattan)

euclid = sum(map(lambda i: i ** 2, x)) ** 0.5
print(euclid)

chebyshev = max(map(abs, x))
print(chebyshev)

C – Cream puff

小さい方から約数を総当りしていく。

1つの約数が見つかればもう片方（大きい約数）も見つかるので、√Nまで探索すればいい。

O(√N)で約数を全列挙でき、制約がN<10^12なので間に合う。

n = int(input())


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


ans = make_divisors(n)
for i in ans:
    print(i)

D – Takahashi Unevolved

最初はDPで実装したがTLE。

A倍するのとB増やす大小関係を比較し、増加量が小さい方を選択し続ければOK。

逐次更新でO（10^9）のように見えるが、ある一定の値を超えるとB増やし続ける段階に入るので、割り算して何回足し込むか求めればO（１）で結果が帰ってくるので間に合う。

x, y, a, b = map(int, input().split())

ans = 0
while x < y:
    if x * a > y and x + b > y:
        break

    if x * a < y and x * a <= x + b:
        x *= a
        ans += 1
    else:
        if (y - x) % b == 0:
            ans += (y - x) // b - 1
        else:
            ans += (y - x) // b
        break

print(ans)