AtCoder Beginners Selection をPythonで解く

はじめに

競技プログラミングをぼちぼちやっています.
復習も兼ねて,Tasks - AtCoder Beginners SelectionPython(3)で解いていきます.

はじめてのあっとこーだー(Welcome to AtCoder

問題文の通りにやるだけです.

def main():
    a = int(input())
    b, c = [int(_) for _ in input().split()]
    s = input()

    print(a + b + c, s)

main()

Product

こちらも問題文の通りにやるだけです. 三項演算子を使っています.

def main():
    a, b = [int(_) for _ in input().split()]
    print("Even") if a * b % 2 == 0 else print("Odd")

main()

Placing Marbles

1の数を数えます.
count関数で特定の文字を文字数を数えることができるのでそれを利用します.

def main():
    print(input().count("1"))

main()

Shift only

全要素を割れなくなるまで2で割り,割れなくなった時のループ回数を表示しています.

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()

Coins

単純な全探索です.
O(n^3)ですが,A, B, Cはたかだか50なので大丈夫.

import sys

def main():
    A = int(input())
    B = int(input())
    C = int(input())
    X = int(input())

    ans = 0

    for nA in range(A + 1):
        for nB in range(B + 1):
            for nC in range(C + 1):
                if nA * 500 + nB * 100 + nC * 50 == X:
                    ans += 1

    print(ans)

main()

Some Sums

str(num)で文字列化し,list(...)によって各文字を要素とする配列に変換し,map(...)によって再度整数型にした後,sum(...)で合計を計算しています.

def main():
    N, A, B = [int(_) for _ in input().split()]

    ans = 0

    for num in range(1, N + 1):
        if A <= sum(map(int, list(str(num)))) <= B:
            ans += num

    print(ans)

main()

Card Game for Two

両者が最適な戦略をとる(=場にある数のうち最大のものを取り続ける)ので,
数を降順に並べ替えた後,
 1, 3, 5, ...番目に大きい数を加算し, 2, 4, 6, ...番目に大きい数を減算すれば良いです.

def main():
    N = int(input())
    A = sorted([int(_) for _ in input().split()], reverse=True)

    ans = 0
    for i, a in enumerate(A):
        if i % 2 == 0:
            ans += a
        else:
            ans -= a

    print(ans)

main()

Kagami Mochi

一見ややこしそうですが,入力値の重複を除くだけで解くことができます.
色々方法はありそうですが,ここでは単純にset関数を用いて集合化することで要素をユニークにしています.

def main():
    N = int(input())
    D = []

    for _ in range(N):
        D.append(int(input()))

    print(len(set(D)))

main()

Otoshidama

全探索しようとするとO(n^3)アルゴリズムになりそうですが,
10000円札の枚数と5000円札の枚数を決定した時点で

1000円札の枚数 = 全体の枚数 - 10000円札の枚数 - 5000円札の枚数

となり1000円札の枚数を決定できるため,計算量をO(n^2)に削減することが可能です.

import sys

def main():
    N, Y = [int(_) for _ in input().split()]

    for n_10k in range(N+1):
        for n_5k in range(N - n_10k + 1):
            n_1k = N - n_10k - n_5k

            if n_10k * 10000 + n_5k * 5000 + n_1k * 1000 == Y:
                print(n_10k, n_5k, n_1k)
                sys.exit()

    print(-1,-1,-1)

main()

白昼夢 / Daydream

 Tに文字列を付け足して Sを作ろうとするのではなく,
 Sから文字列を削除することで T(=空文字列)を作ることができるかを調べます.

ここで,前方から検索すると,dreamerereraseerが混じって面倒です.
後方から検索を行うことで,erに関係なく Sから文字列を削除することが可能です.

def main():
    S = input()

    while len(S) >= 5:
        if len(S) >= 7 and S[-7:] == "dreamer":
            S = S[:-7]
            continue

        if len(S) >= 6 and S[-6:] == "eraser":
            S = S[:-6]
            continue

        elif S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue

        else:
            break

    if len(S) == 0:
        print("YES")
    else:
        print("NO")

main()

Traveling

AtCoDeerくんが時刻  t に座標  (x, y) にいるとします.
そして,時刻  t' に座標  (x', y') に移動しなければいけない状況を考えます.

ここで, distance = |(x' - x)| + |(y' - y)|とします.
また, timedelta = t' - t とします.

 distance > timedelta であるとき,つまり移動量が移動可能時間よりも大きいとき,時間内に移動を終えることは不可能です.
よって,Noを出力して終われば良いです.

 distance = timedelta であるとき,つまり移動量と移動可能時間が同じとき,時間内に移動を終えることが可能です.
よって,Yesを出力し次の条件に移ります.

 distance \lt timedelta であるとき,つまり移動量より移動可能時間が大きいときは,条件を達成できる場合とできない場合があります.

例えば,時刻  0 に座標  (0, 0) にいて,時刻  4 に座標  (2, 0) に移動しなければならない時は (0, 0), (1, 0),  (2, 0),  (1, 0),  (2, 0)のように,目的の座標にたどり着いた後行ったり来たりを繰り返せば条件を達成することができます.

一方で,時刻  0 に座標  (0, 0) にいて,時刻  5 に座標  (2, 0) に移動しなければならない時は (0, 0),  (1, 0),  (2, 0),  (1, 0),  (2, 0),  ...となり,どう歩いても目的の座標に目的の時刻にたどり着くことは不可能です.

まとめると, distance \lt timedelta であるときは,ゴールにたどり着いた後,行ったり来たりして残り時間を消費できれば条件を達成することができるといえます.

これは, timedelta - distance の値,つまり目的地にたどり着いた後の余裕時間が  2 で割り切れるかを調べるとわかります.
なぜなら,目的地にたどり着いた後の余裕時間の値が  2 で割り切れるとき,行ったり来たりして目的の座標に戻ることができるからです.

import sys

def main():
    N = int(input())
    t, x, y = 0, 0, 0

    for _ in range(N):
        next_t, next_x, next_y = [int(__) for __ in input().split()]

        delta_t = next_t - t
        distance = abs(next_x - x) + abs(next_y - y)

        if distance > delta_t:
            print("No")
            sys.exit()

        if (delta_t - distance) % 2 != 0:
            print("No")
            sys.exit()

        t, x, y = next_t, next_x, next_y

    print("Yes")

main()

おわりに

はやく水色になりたい