AtCoder Beginners SelectionにPythonで挑戦

この記事では、AtCoder Beginners SelectionにPythonで挑戦します。

Atcoderに登録したものの、次に何をすれば良いのかわからない方に向けて、Atcoderから最初に解いてみると良いよということで用意してくれている問題です。

この記事では私が挑戦した記録と解答を載せていきます。

全部で10問あるので、4問目くらいまでは自力で解けるとうれしいです。

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
10問解けたら次のステップへ

PracticeA – Welcome to AtCoder

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

a=int(input())

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

s=input()

print(a+b+c,s)

ABC086A – Product

a,b = map(int, input().split())
if a*b%2!=0:
  print('Odd')
else:
  print('Even')

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

if a*b%2!=0:

print('Odd')

else:

print('Even')

ABC086のA問題からの出題でした。

ちなみにABC086はこちらの記事で挑戦しています。

【Python】AtCoder Beginner Contest 086 A問題解答

ABC081A – Placing Marbles

s = input()
print(s.count('1'))

1 2	s = input() print(s.count('1'))

ABC081のA問題からでした。

こちらの記事で挑戦しています。

【Python】AtCoder Beginner Contest 081 A問題解答

ABC081B – Shift only

import numpy as np

n = int(input())
list = list(map(int,input().split()))
list = np.array(list)

flag=False
count =0
while count >=0:
  for i in list:
    if i%2!=0:
      flag=True
      break
  if flag:
    break
  count+=1
  list = list//2
  
print(count)

import numpy as np

n = int(input())

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

list = np.array(list)

flag=False

count =0

while count >=0:

for i in list:

if i%2!=0:

flag=True

break

if flag:

break

count+=1

list = list//2

print(count)

こちらの記事で挑戦しています。

【Python】AtCoder Beginner Contest 081 解答

ABC087B – Coins

# X = a*p + b*q + c*r

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):
      #print(i,j,k)
      if i*500 + j*100 + k*50 == x:
        ans += 1
print(ans)

# X = a*p + b*q + c*r

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):

#print(i,j,k)

if i*500 + j*100 + k*50 == x:

ans += 1

print(ans)

ABC083B – Some Sums

n,a,b = input().split()
N = int(n)
ans = 0
for j in range(1,N+1):
  sum = 0
  J = [int(x) for x in list(str(j))]
  for i in range(len(J)):
    sum = sum + J[i]
  if int(a) <= sum <= int(b):
    ans = ans + j
print(ans)

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

N = int(n)

ans = 0

for j in range(1,N+1):

sum = 0

J = [int(x) for x in list(str(j))]

for i in range(len(J)):

sum = sum + J[i]

if int(a) <= sum <= int(b):

ans = ans + j

print(ans)

ABC088B – Card Game for Two

import  numpy as np

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

a= np.array(a)
list1 = a[1::2]
list2 = a[::2]

print(abs(np.sum(list1)-np.sum(list2)))

import numpy as np

n = int(input())

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

a = sorted(a)

a= np.array(a)

list1 = a[1::2]

list2 = a[::2]

print(abs(np.sum(list1)-np.sum(list2)))

降順のリストにして、numpy配列にし、奇数番目と偶数番目の合計の差の絶対値を出力しました。

参考

NumPy配列の要素の合計を求めるsum関数の使い方 | HEADBOOST

Numpyの配列をN個飛ばしで列挙する簡単な方法 | Shikoan’s ML Blog

こちらの方がシンプルで早いですね。

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
alice,bob=0,0
for i in range(n):
    if i%2==0:
        alice+=a[i]
    else:
        bob+=a[i]
print(alice-bob)

n=int(input())

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

a.sort(reverse=True)

alice,bob=0,0

for i in range(n):

if i%2==0:

alice+=a[i]

else:

bob+=a[i]

print(alice-bob)

ABC085B – Kagami Mochi

n = int(input())
list = []
for i in range(n):
  list.append(int(input()))
print(len(set(list)))

n = int(input())

list = []

for i in range(n):

list.append(int(input()))

print(len(set(list)))

入力された値をリストにし、setで重複をなくした後の要素数を出力しました。

ABC085C – Otoshidama

"""
n：お札の枚数
y：合計金額
a:10000
b:5000
c:1000

y = 10000*a+5000*b+1000*c
n=a+b+c
c=n-(a+b)
"""
n,y = map(int,input().split())

for a in range(n+1):
  for b in range(n-a+1):
    c=n-(a+b)
    if 10000*a+5000*b+1000*c==y:
      print(a,b,c)
#      print(a*10000+b*5000+c*1000)
      exit()
    c+=1
      
print('-1 -1 -1')

"""

n：お札の枚数

y：合計金額

a:10000

b:5000

c:1000

y = 10000*a+5000*b+1000*c

n=a+b+c

c=n-(a+b)

"""

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

for a in range(n+1):

for b in range(n-a+1):

c=n-(a+b)

if 10000*a+5000*b+1000*c==y:

print(a,b,c)

# print(a*10000+b*5000+c*1000)

exit()

c+=1

print('-1 -1 -1')

問題文から最初に式を立ててみました。

式①：y = 10000*a+5000*b+1000*c

式②：n=a+b+c

式③：c=n-(a+b)

式③から、cはaとbが決まれば求まります。

aとbを全探索する中でa,b,cの合計がn枚の時で、

a,b,cにそれぞれのお札の金額を掛けた合計がy円になる時、(つまり式①が成り立つ時)

a,b,cの枚数を表示しました。

ABC049C – 白昼夢

s=input()
list = ['dream','dreamer','erase','eraser']

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


if len(s)==0:
  print('YES')
else:
  print('NO')

s=input()

list = ['dream','dreamer','erase','eraser']

s=s.replace('eraser','')

s=s.replace('erase','')

s=s.replace('dreamer','')

s=s.replace('dream','')

if len(s)==0:

print('YES')

else:

print('NO')

解説を見て解答しました。

入力された文字列sの中に、listの中にある文字列があれば削除していき、sが空になればYES,そうでなければNOを出力します。

文字列を削除する順番が重要なようです。削除する順番によってYESのはずがNOと解答してしまう場合があります。

例を書きます。入力された文字列はここでは見やすいように半角スペースをいれています。

例1）入力：dreamer dream

dreamerよりdreamを先に削除した場合、残る文字はerdreamとなり、ＮＯになります。

しかしdreamerを削除すると残る文字はdreamとなり、YESになります。

例2）入力：dream erase

dreamerを削除した場合、残る文字はaseでNO

dreamを削除した場合、残る文字はeraseでYES

このようなことになるので、削除の順番はeraser→erase→dreamer→dreamが正しいです。

この順番を守って、前から順に前から順に一致した文字列を削除していく方法を考える問題だと思います。

ただ、Pythonはとても強力でした。replace()を使うと、文字列の中で一致した部分が全て削除されます。

例）入力：dreamer dream erase dreamer

この入力された値をsに代入した後、s.replace(‘dreamer’,”)とすると、

最初と最後のdreamerが削除され、残る文字はdream eraseとなります。

文字列の途中から削除をすると、先ほどのように望ましくない削除が行われてしまうかもしれないので、先頭から削除していくことを考える方が多いのではないかと思うのですが、

先ほどの順番を守った上で、replace()で削除していけば解答できるようです。

Pythonが優秀なのでこれで良いのか？とは若干思いますが、Pythonの言語仕様の理解が一歩進んだので良しとします。

ABC086C – Traveling

n=int(input())
list = []
for i in range(n):
  a=input().split()
  list.append(a)

if n==1:
  t = int(list[0][0])               
  d = int(list[0][1]+list[0][2])    
  if t<d:                           #条件1　移動距離に必要な時間がない場合
    print('No')
    exit()
  else:                             
    if (t+d)%2!=0:　                #条件2　目的地への到着時、残り秒数が偶数でない場合
      print('No')
      exit()

else:
  for i in range(n-1):  
    t = int(list[i+1][0])-int(list[i][0])
    d=abs((int(list[i+1][1])+int(list[i+1][2])) - (int(list[i][1])+int(list[i][2])))
    if t < d:                 #条件1　移動距離に必要な時間がない場合
      print('No')
      exit()
    else:                        
      if (t+d)%2!=0:          #条件2　目的地への到着時、残り秒数が偶数でない場合
        print('No')
        exit()

print('Yes')

n=int(input())

list = []

for i in range(n):

a=input().split()

list.append(a)

if n==1:

t = int(list[0][0])

d = int(list[0][1]+list[0][2])

if t<d: #条件1　移動距離に必要な時間がない場合

print('No')

exit()

else:

if (t+d)%2!=0:　 #条件2　目的地への到着時、残り秒数が偶数でない場合

print('No')

exit()

else:

for i in range(n-1):

t = int(list[i+1][0])-int(list[i][0])

d=abs((int(list[i+1][1])+int(list[i+1][2])) - (int(list[i][1])+int(list[i][2])))

if t < d: #条件1　移動距離に必要な時間がない場合

print('No')

exit()

else:

if (t+d)%2!=0: #条件2　目的地への到着時、残り秒数が偶数でない場合

print('No')

exit()

print('Yes')

二次元平面上で、それぞれの時刻にそれぞれの目的地に移動することができるかという問題です。

ルールはこちらの通りです。

・時刻0、座標(0,0)からスタートする

・1秒につき、(x±1,y)もしくは(x,y±1)のように1回移動できる

・毎秒必ず移動しなければならない

例1）入力例1を例に考えてみます。

入力値

2
3 1 2
6 1 1

2は入力回数のことです。3秒目の時点で座標(1,2)へ、6秒目の時点で座標(1,1)にいることができればYes、できなければNoと出力します。

解答するためには2つの条件について判定します。

条件1：時間内に移動できるか

条件2：指定された時刻に指定された座標にいられるか

条件1について、入力例2を例にして考えてみます。

入力

1
2 100 100

2秒目の時点で、座標(100,100)にいなければなりません。

座標(0,0)からスタートして、1秒間で移動できるのは(0,1)か(1,0)のどちらかなので、(100,100)に移動するには200秒必要です。↓入力値がこのようになっていればOKだと思います。

1
200 100 100

条件2について考えてみます。

制限時間内に一度でも目的地にたどりつけば良いのではなく、指定された時刻にピッタリその座標にいなければなりません。

先ほどの入力値だと、2秒後にピッタリ座標(100,100)にいなければなりません。

1
2 100 100

ですが、常に移動しなければならないというルールがあるので、目的地についたら時間まで待つこともできないので、別の方法が必要になります。

といっても、目的についた時点で残り秒数が偶数であるかというだけになります。

到着後、隣の座標と行ったり来たりを繰り返せば良いからです。

なので、この2つの条件を判定することができるようコードを書いてみました。

10問解けたら次のステップへ

10問解ききることができました。

初心者が次にするべきことは次の3つになります。

・毎週のAtcoder Beginner Contestに参加する

→参加回数が低いうちはレーティングが低くなる仕様になっています。

開催は1週間に1度です。10回参加するのにも2か月半かかります。慣れが一番です。

・Atcoder Problemsで過去の問題を解く

→そのまま、これまでのAtcoder Beginner Contestの過去問を解くことができます。慣れが一番です。

・データ構造とアルゴリズムの勉強をする

→解くために知っておくべきことが多いことも事実です。勉強をした上でもう一度問題にあたってみると今までとは違った景色が見えてきます。

勉強するにあたり、参考になる書籍は以下の通りです。

よく勧められている書籍2冊を先に紹介します。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテストチャレンジブック

これら2冊は他のサイトでも非常に多く紹介されています。レビューを読んでも高評価が非常に多いです。が、コードがC++で書かれています。

Pythonで解いている私はそもそもコードがわからなくて勉強になりませんでした。

そこで、まずはデータ構造とアルゴリズムについて概要だけでも良いので知ってみようと思い購入した本が次の本です。

問題解決力を鍛える！アルゴリズムとデータ構造

文体も難しくなく、コードも多すぎず、初めて触れるのに良い本だと思いました。レビューも高評価な内容が多いです。

正直なところ、この本を読んで役に立つのはAtcoderだと茶色以上に上がってからだと思いますが、早めに知ることが重要です。

また、知っている状態から使える状態になるまでにもある程度の時間がかかりますし、初めて触れる分野は本を1回読んだだけで十分に理解するのも難しいかと思います。

コンテストへの参加と過去の問題を解きつつ、並行して進められれば効率が良いです。

この本を読み終えたところで、やっぱりPythonのサンプルコードがあって読みやすい本が欲しいなと思い、購入したのが次の本です。

写経して、1行ずつコードを読んでいくことで何とか動きが理解できると思います。

Pythonで始めるアルゴリズム入門

最初の2冊を購入した後で追加で2冊購入して合計4冊になりましたが、

初心者の段階ではこの4冊があれば十分すぎるほどであり、全てを読み終えるころには初心者脱出できるのではないかと思います。