【競プロ練習】AtCoder Beginner Selectionをやってみた

つい1週間前にAtCoderを初め、そのときにAtCoder Beginners Selection をやってみました。
競技プログラミングとうものに初めて触れたので、入力方法を学ぶことから初めました。
自分なりにどう考えたのかということと、解答をまとめました。

PracticeA - Welcome to AtCoder

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

print('{} {}'.format(a+b+c,s))

入出力関連のテスト
int(input())
map(int, input().split())
後々他のコンテストを解くに連れて、この2つは多用することを知りました。

ABC086A - Product

strings = ['Even','Odd']
a, b = map(int, input().split())

print(strings[(a*b)%2])

奇遇を解答する問題。

ABC081A - Placing Marbles

#Placing Marbles
S = list(input())
print(S.count('1'))

入力数値から1である桁数を求める問題。
文字列として入力し個数を判定しました。

ABC081B - Shift only

#Shift only
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
count = 0
check = A%2
while np.count_nonzero(check)==0 :
    count += 1
    A = A/2
    check = A%2

print(count)

入力配列を何回2で割り切れるかとい問題。
numpy array では演算子は各要素に適用されるため、入力をnumpyに受けて解答しています。
今思うと、わざわざcheckという変数に受ける必要はなかった気がする……。

ABC087B - Coins

#Coins
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count=0
for i in range(A+1):
    yo = X-i*500
    if(yo>=0):
        for j in range(B+1):
            yoi = yo-j*100
            if(yoi>=0):
                for k in range(C+1):
                    yoii = yoi-k*50
                    if(yoii==0):
                        count +=1

print(count)

500円玉A枚、100円玉B枚、50円玉C枚からX円を作る組み合わせの数。

解答の方針は
500円玉を0枚に固定して、100円玉ループ。
100円玉ループでは100円玉0枚に固定して50円玉ループ。
50円玉C枚以下でX円が生成できたら、上位の100円玉ループに戻り、100円玉を1枚として……以下略
for文が多重化してるのでなんとか簡単にしたいなと思いつつこれが限界でした。

ABC083B - Some Sums

#Some Sums
N, A, B = list(map(int, input().split()))
count = 0
for j in range(N):
    S = str(j+1)
    numN = 0
    for i in range(len(S)):
        numN += int(S[i])
    if A <= numN <= B:
        count += j+1
print(count)

1<=x<=NかつA<=各桁の和<=Bであるすべての整数xの総和。
数字をstrになおして各桁をintで受けてfor文で総和を求めました。

反省点
3入力を3変数で受けるのでlistにする必要はなかった。
range(1,N+1)で1からNを計算できたこと。
sumメソッドが活用できた（？）

ABC088B - Card Game for Two

#Card Game for Two
N = int(input())
a = sorted(map(int, input().split()))
count = 0
for i in range(N):
    count += a[-i-1] * (-1)**i
print(count)

任意の数字が書かれたN枚のカードをAliceとBobが得点が最大となるよう交互に取得していく。最後にAliceとBobの得点差を求める問題。

N枚のカードを大きい順にソートし、奇数番目をAlice、偶数番目をBobにわたす。
↓
最終的に得点差を求めるため、奇数番目を足し、偶数番目を引くとよい。
このように考え解答しました。

ABC085B - Kagami Mochi

import numpy as np
N = int(input())
d = np.zeros(N)
for i in range(N):
    d[i] = int(input())
sorted_d = np.unique(d)
print(len(sorted_d))

N個の円盤の直径が与えられ、それを上より下が大きい順に積んだとき最大何段積むことができるかという問題。

同じ直径の円盤は重ねることはできない。
↓
Numpyのuniqueな配列を返す関数を利用することで、重複しない配列を入手できる。その要素数を求める。
このとうに考え解答しました。

ABC085C - Otoshidama

#Otoshidama
N, Y = list(map(int, input().split()))
y_man = Y
flag = False
out = [-1,-1,-1]
for i in range(N+1):
    y_gsen = y_man
    for j in range(N-i+1):
        n_sen = int(y_gsen/1000)
        if N-i-j == n_sen:
            out = [i,j,n_sen]
            flag = True
            break
        y_gsen -= 5000
    if flag:
        break
    y_man -= 10000
print('{} {} {}'.format(out[0],out[1],out[2]))
# print(out[0]*10000+out[1]*5000+out[2]*1000)

1万円札、5千円札、千円札合わせてN枚、Y円が可能かどうか。可能ならその組み合わせを解答（不可能なら-1 -1 -1）

下層のfor文から抜けた場合、上層のfor文も抜けるという方法が検索したらでてきましたが、理解が難しくflagという変数を設けることで代用しました。

ABC049C - 白昼夢

#Hakuchumu
S = input()
m = ['dream','dreamer','erase','eraser']
for i in range(len(m)):
    m[i] = m[i][::-1]
lenS = len(S)
revS = S[::-1]
Header = 0
flag = True
Ans = 'YES'

while Header < lenS-1 :
    flag = True
    if Header + 6 < lenS:
        # print('6t')
        if revS[Header:Header+7]==m[1]:
            Header += 7
            flag = False
            # print('6tt')

    if Header + 5 < lenS:
        # print('5t')
        if revS[Header:Header+6]==m[3]:
            Header += 6
            flag = False
            # print('5tt')

    if Header + 4 < lenS:
        # print('4t')
        if revS[Header:Header+5]==m[0] or revS[Header:Header+5]==m[2]:
            Header += 5
            flag = False
            # print('4tt')
    if flag:
        Ans = 'NO'
        # print('out')
        break

print(Ans)

文字列Sを'dream','dreamer','erase','eraser'の4を任意に並べることで完成できるか判定する問題。

文字列の先頭から判定し、一致すればその文字数分Headerを動かすという方法を考えましたが、dreameraseなどの分け方が複雑な文字列の条件分岐に敗北しました。
文字列を反転させると、一致することがないというヒントを元に完成させた解答です。

ABC086C - Traveling

#Traveling
import numpy as np
N = int(input())
Plan = np.zeros((N+1,3))
for i in range(N):
    Plan[i+1] = list(map(int, input().split()))

able = 'Yes'
for j in range(N):
    t, x, y = Plan[j]
    t_next, x_next, y_next = Plan[j+1]
    distance = abs(x-x_next) + abs(y-y_next)
    delta = t_next - t
    amari = delta - distance
    # print(distance,delta,amari)
    if amari < 0 or amari%2 == 1:
        able = 'No'
        break

print(able)

1時刻に上下左右いずれか1マスの格子点に必ず移動するとき、時刻t_nにx_n,y_nに存在するという組み合わせが実現可能かという問題。

まず、次のx,yの距離がtより小さいことを判定します。そして、必ず移動するというのを考慮し、あまりの時刻が偶数である場合、実現可能。奇数の場合、必ず移動しなければならないため到達不可能ということを判定しました。

まとめ

今見直すと、いろいろ改善点がありました。
次のコンテストに向けて精進精進……。