AtCoder Beginners Selection を解く

こんにちは、zawato（@zawato7）です！

前回からの続き。

今回は、AtCoder Beginners Selection を解いていく。

PracticeA – Welcome to AtCoder
ABC086A – Product
ABC081A – Placing Marbles
ABC081B – Shift only
ABC087B – Coins
ABC083B – Some Sums
ABC088B – Card Game for Two
ABC085B – Kagami Mochi
ABC085C – Otoshidama
ABC049C – 白昼夢
ABC086C – Traveling
おわりに

PracticeA – Welcome to AtCoder

前回記事で扱った問題と同じため割愛。

ABC086A – Product

偶奇を判定する問題。

あまりに注目して、条件分岐させる。

Pythonコード例

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

if (a * b) % 2 == 0:
    print("Even")
else:
    print("Odd")

ABC081A – Placing Marbles

文字列の中に含まれる”１”をカウントする問題に置き換える。

シンプルに str型の count()メソッド を使えば良さそう。

Pythonコード例

s = input()

print(s.count("1"))

ABC081B – Shift only

与えられた整数が偶数である場合に、すべての整数を２で割る操作を繰り返す問題。

整数をリストで受け取って、while文でループさせてみる。

Pythonコード例

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

cnt = 0 # 操作回数の初期化

while all(x % 2 == 0 for x in a):
    a = [x // 2 for x in a]
    cnt += 1

print(cnt)

ABC087B – Coins

全組み合わせを探索する力技で解く。

Xと一致したら、カウントを増やす。

Pythonコード例

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

cnt = 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:
                cnt += 1

print(cnt)

ABC083B – Some Sums

10 進法での各桁の和を求める関数を用意して、条件を満たしたらカウントを増やす。

各桁の和を求めるには、文字列に変換した後、配列の要素を数値に戻して和を計算する。

Pythonコード例

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

def sum_digits(n):
    return sum(int(d) for d in str(n))

cnt = 0

for i in range(1, n+1):
    if a <= sum_digits(i) <= b:
        cnt += i

print(cnt)

ABC088B – Card Game for Two

カードを使ったゲームに関する問題。

「2人とも自分の得点を最大化するように最適な戦略を取る」＝「場の中で最大の数字が書かれたカードから取る」と読み替えられる。

ソートした配列から、交互に値を取っていくように実装。

Pythonコード例

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

a.sort(reverse=True) # 降順に並び替える

alice = 0
bob = 0

for i in range(n):
    if i % 2 == 0:
        alice += a[i]
    else:
        bob += a[i]

print(alice - bob)

ABC085B – Kagami Mochi

重複する値を除外して、残った枚数が最大で重ねられる鏡餅の段数になる。

順番は関係なく重複を除外する場合は、list ではなく set を利用するのが良さそう。

Pythonコード例

n = int(input())
d = set()

for _ in range(n):
    d.add(int(input())) # 重複は追加されない

print(len(d))

ABC085C – Otoshidama

全組み合わせを探索する力技で解く。

枚数がN枚と決まっているので、２重ループで実装できそう。

Pythonコード例

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

for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit() # 強制終了

print(-1, -1, -1)

ABC049C – 白昼夢

特定の単語を連結して、指定の文字列と一致するか判定する問題。

dream, dreamer, erase, eraserのそれぞれで被る箇所があるのが厄介。

文字列の後ろから見ていく方が確実と考えられる。

Pythonコード例

s = input()

word_list= ["dream", "dreamer", "erase", "eraser"]

while s:
    matched = False
    for w in word_list:
        if s.endswith(w):
            s = s[:-len(w)]
            matched = True
            break
    if not matched:
        print("NO")
        exit()

print("YES")

ABC086C – Traveling

二次元平面を移動する問題。

旅行プランが実行可能であるための条件は以下の２つ。

時間が足りるか
→距離よりも時間が短い場合は到達不可能。
偶奇が一致するか
→余った時間を「その場から移動して戻る」で消費できるのは、偶数時間だけ。
　奇数分余ってしまうと、ぴったり到達できない。

全ての2地点間で上記の条件に一致した場合のみ、実行可能であると判定すれば良い。

※開始地点(0, 0)を考慮するのを忘れずに！

Pythonコード例

n = int(input())
t = [0] * (n + 1)
x = [0] * (n + 1)
y = [0] * (n + 1)

for i in range(n):
    t[i+1], x[i+1], y[i+1] = map(int, input().split())

for i in range(n):
    d = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i])
    if (t[i+1] - t[i]) < d:
        print("No")
        exit()
    if ((t[i+1] - t[i]) - d) % 2 != 0:
        print("No")
        exit()
        
print("Yes")