🐈

AtCoder Beginners SelectionをPythonで解いてみた

に公開
Python
初心者
AtCoder
tech

はじめに

今回はAtCoderBeginnersSelectionをPythonで解いてみたので、参考程度に解答と解説を載せておきます。
https://atcoder.jp/contests/abs

ABC081B - Shift only

n = int(input())
a = list(map(int,input().split()))
ans = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i]/2
        else:
            print(ans)
            exit()
    ans +=1
print(ans)

全てを2で割るのを繰り替えし、一つでも割り切れなかったら終了します。繰り替えしが成功するごとにカウントを増やします。
mapとで受け取ってlistに格納する方法は良く出てきます！

ABC087B - Coins

a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0

for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500+j*100+k*50 ==x:
                ans += 1

print(ans)

3重ループは本当はしたくないですが、制約から最悪でも50^3~= 10^6なので大丈夫かなという感じです。
一般に約10^8~10^9を超える計算はTLEとなるそうです。
もし超える場合は何かしらのアルゴリズムを使うなど、工夫が必要です。

ABC083B - Some Sums

n, a, b = map(int,input().split())
ans = 0

for i in range(1,n+1):
    if a<= sum(map(int,str(i))) <=b:
        ans += i

print(ans)

int型の数の各桁をリストに格納して合計を取ります。

ABC088B - Card Game for Two

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
alice = sum(a[::2])
bob = sum(a)-alice

print(alice-bob)

降順にソートし、交互に取るため、aliceは配列の初めから2個置きのものの合計が得点となると考えられます。bobはすべてからaliceの点を引いたものが得点となる。

ABC085B - Kagami Mochi

n = int(input())

a = set()

for i in range(n):
    d = int(input())
    a.add(d)

print(len(a))

重複を許さないsetに入れていけば必然的にお餅の要素になると考えられます。重複なしかつ昇順に並べられる数字が集まりますね。

ABC085C - Otoshidama

n, y = map(int, input().split())

for i in range(n+1):
    for j in range(n+1):
        k = n-(i+j)
        if (i+j <= n) and (10000*i+5000*j+1000*k == y):
            print(i, j, k)
            exit()

print(-1, -1, -1)

最後のkについて少し工夫をするとうまくいきます。
この手法はたまに見かけます。

ABC049C - 白昼夢

s = input()

s = s.replace("eraser", "")
s = s.replace("erase", "")
s = s.replace("dreamer", "")
s = s.replace("dream", "")

print("YES" if s == "" else "NO")

sをどんどんreplaceしていって、無になればtはsから作れることになりますね。
ポイントは文字数が長いほうから削除していくことです。

ABC086C - Traveling

n = int(input())
pre_t, pre_x, pre_y = 0, 0, 0

for _ in range(n):
    t, x, y = map(int, input().split())
    dt = t - pre_t
    dist = abs(x - pre_x) + abs(y - pre_y)
    if dist > dt or (dt - dist) % 2 != 0:
        print("No")
        exit()
    pre_t, pre_x, pre_y = t, x, y

print("Yes")

到達可能なためには、

  1. 時間内で移動できるかdist > dt
  2. 余り分が偶数か(dt - dist) % 2 != 0

の確認が必要です。

一つ目についてはマンハッタン距離distを用いて比較します。
上下左右のマスではxの変位とyの変位の和で距離を表現できますね。この距離が時間よりも長かったら到達は不可能です。

二つ目については、偶奇に着目します。
ここで大切なことはピッタリついた場合と比較して、
時間が余った場合には、寄り道する必要が発生します。
この寄り道とは、どこかに行って、また戻ってくる必要があります。
ということは寄り道分(寄り道の片道×2)は偶数でなければなりません。
補足として、寄り道の時間は(時間-距離)で求まります。

Discussion