AtCoder Beginners Selection 徹底解説【Python】

2020年2月29日 02:15

AtCoder に登録したらまず解くであろう AtCoder Beginners Selection を徹底的に解説します。

言語は Python ですが、競技プログラミングの核はアルゴリズムなので他の言語でも応用できる部分があると思います。

問題文は掲載しないので、下記のリンクから AtCoder にログインして確認してください。

PracticeA - Welcome to AtCoder

解法：入力された数字と文字列を出力するだけですが、数字を計算するため整数型に直し忘れないようにしましょう。

# コード
a = int(input())
b, c = map(int, input().split())
s = input()
print("{} {}".format(a+b+c, s))

# 入力
1
2 3
test

# 出力
6 test

--- コード解説 ---

a = int(input())

input() で標準入力から '1' を取得する。

int('1') でキャスト（型変換）して 1 にする。

a に 1 を代入する。

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

input().split() で標準入力から ['2', '3'] を取得する。

map(int, ['2', '3']) でキャスト（型変換）して [2, 3] にする。

b に 2 を、c に 3 を代入する。

s = input()

input() で標準入力から 'test' を取得して s に代入する。

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

a+b+c は 6 。

s は 'test' 。

"{} {}".format(6, 'test') で最初の {} が 6 に、二番目の {} が 'test' に置き換わる。

print("6 test") で "6 test" を標準出力する。

--- コード解説終わり ---

ABC086A - Product

解法：偶数か奇数かを判定するために 2 で割った余りが 0 か 1 かで判断します。

# コード
a, b = map(int, input().split())
if (a*b) % 2:
  print('Odd')
else:
  print('Even')

# 入力
3 4

# 出力
Even

--- コード解説 ---

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

input().split() で標準入力から ['3', '4'] を取得する。

map(int, ['3', '4']) でキャスト（型変換）して [3, 4] にする。

a に 3 を、b に 4 を代入する。

if (a*b) % 2:
  print('Odd')
else:
  print('Even')

(a*b) は 3*4 で 12 。

12 % 2 は 0 。

if 0: は if False: と同じなので else の処理へ。

print('Even') で 'Even' を標準出力する。

--- コード解説終わり ---

ABC081A - Placing Marbles

解法：入力では '0' か '1' のみ入力されるため単純に文字列から '1' の数を数えるだけです。

# コード
print(input().count('1'))

# 入力
101

# 出力
2

--- コード解説 ---

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

input() で標準入力から '101' を取得し、.count('1') で取得した文字列から '1' の数を数えて 2 を得る。

print(2) で 2 を標準出力する。

--- コード解説終わり ---

Python では .count() メソッドが使えるため、一行で問題を解くことができます。文字列操作に強い Python ならではの解き方ではないでしょうか。

ABC081B - Shift only

解法：与えられた数字全てが 2 で何回割れるのかを求める問題ですが、タイトルがヒントになっており 2 進数に直してからシフトすることで解けるでしょう。今回はシフトできる最大の数、つまり与えられた数字全てを 2 進数に変換し、1 が出てくるまでは右シフトすることができるので、その最大値を求めます。

# コード
n = input()
a = list(map(int, input().split()))
ans = float('inf')
for i in a:
  ans = min(ans, len(bin(i)) - bin(i).rfind('1') - 1)
print(ans)

# 入力
3
8 12 40

# 出力
2

--- コード解説 ---

n = input()

input() で標準入力から '3' を取得する。

n に '3' を代入する。

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

input().split() で標準入力から ['8', '12', '40'] を取得する。

map(int, ['2', '3']) でキャスト（型変換）して [8, 12, 40] にする。

map() はイテレータなのでリストとして扱うために list([8, 12, 40]) で変換する。

a に [8, 12, 40] を代入する。

ans = float('inf')

float('inf') で ∞ (無限大)を作る。

ans に ∞ を代入する。

Python で無限大を表現する場合は、float型に inf を入れる事で作ることができる。

for i in a:
  ans = min(ans, len(bin(i)) - bin(i).rfind('1') - 1)

for i in a: で a の要素 [8, 12, 40] だけループする。

bin(i) で 10 進数を 2 進数に変換する。i が 8 の場合 bin(8) は '0b1000' に変換される。

len('0b1000') で文字列の文字数 6 を得る。

bin(8).rfind('1') は文字列 '0b1000' から最後に見つけた '1' の位置 2 を得る。

.rfind() メソッドは最後に見つけた物の位置を返すが、位置は文字列の先頭 0 番目から数えている事に注意する。今回の場合は 0 が 0 番目, b が 1 番目, 1 が 2 番目で、これ以降 1 は現れないため 2 が得られる。

6 - 2 - 1 は 3 。つまり 8 は 2 で 3 回まで割ることができます。

min(∞, 3) で小さい方の要素 3 を得る。

ans に 3 を代入する。

a の要素数だけ繰り返す。

print(ans)

print(2) で 2 を標準出力する。

--- コード解説終わり ---

Python では .split() メソッドで複数の標準入力を取得できるため n は使いませんでした。他の言語では n を使って n 回ループで標準入力から 1 つずつ数字を取得することもあります。

ABC087B - Coins

解法：コインの枚数には制限があるので、全ての組み合わせを試して x と一致する組み合わせが何通りあるのかを数えます。

# コード
a, b, c, x = map(int, [input() for i in range(4)])
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)

# 入力
2
2
2
100

# 出力
2

--- コード解説 ---

a, b, c, x = map(int, [input() for i in range(4)])

input() for i in range(4) で input() を 4 回繰り返して ['2', '2', '2', '100'] を取得する。

今回の問題は入力形式が縦に 4 つ並んでいる形式のため for 文で繰り返す形を取っています。a = int(input()) というコードを 4 つ縦に書くのを省略した書き方です。

map(int, ['2', '2', '2', '100']) でキャスト（型変換）して [2, 2, 2, 100] にする。

a に 2 を、b に 2 を、c に 2 を、x に 100 を代入する。

ans = 0

ans に 0 を代入する。

この変数は x と一致する組み合わせをカウントする物ですが、0 を初期代入することで変数が 0 で初期化されないリスクを無くしたり、変数が整数型 (int) であることを示すことができます。

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):

a, b, c のコインの数だけ for 文を回し、全ての組み合わせを試す。

3 重 for ループを回すと

[i, j, k] =

[0, 0, 0] [0, 0, 1] [0, 0, 2] [0, 1, 0] [0, 1, 1] [0, 1, 2] [0, 2, 0] [0, 2, 1] [0, 2, 2]
[1, 0, 0] [1, 0, 1] [1, 0, 2] [1, 1, 0] [1, 1, 1] [1, 1, 2] [1, 2, 0] [1, 2, 1] [1, 2, 2]
[2, 0, 0] [2, 0, 1] [2, 0, 2] [2, 1, 0] [2, 1, 1] [2, 1, 2] [2, 2, 0] [2, 2, 1] [2, 2, 2]

の順に代入される。

range(a+1) は range(2+1) となるが、range() 関数は 0 から (括弧の中の数 - 1 ) までのループを回すため注意が必要。

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

x とコインの合計が一致した場合 ans += 1 で ans のカウントを 1 増やす。

print(ans)

print(2) で 2 を標準出力する。

今回 x (100) と一致する組み合わせは [0, 1, 0] [0, 0, 2] の 2 通り。

--- コード解説終わり ---

ABC083B - Some Sums

解法：数字の各桁を合計するために、一度整数を文字列に変換し、桁をバラバラにしてからもう一度文字列を整数に変換し合計する。

# コード
n, a, b = map(int, input().split())
ans = 0
for i in range(n+1):
  if a <= sum(list(map(int, list(str(i))))) <= b:
    ans += i
print(ans)

# 入力
20 2 5

# 出力
84

--- コード解説 ---

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

input().split() で標準入力から ['20', '2', '5'] を取得する。

map(int, ['20', '2', '5']) でキャスト（型変換）して [20, 2, 5] にする。

n に 20 を、a に 2 を、b に 5 を代入する。

ans = 0

ans に 0 を代入する。

for i in range(n+1):

range(20+1) で 0 から 20 までループする。

  if a <= sum(list(map(int, list(str(i))))) <= b:
    ans += i

今回は i が 13 のときの解説をします。

str(i) で 13 を '13' にキャストする。

list('13') で '13' を ['1', '3'] に分割する。

map(int, ['1', '3']) で ['1', '3'] を [1, 3] にする。

list([1, 3]) でイテレータをリストにする。

sum([1, 3]) で 4 を得る。

if 2 <= 4 <= 5: は if True なので ans += i で ans の値を 13 増やす。

print(ans)

print(84) で 84 を標準出力する。

--- コード解説終わり ---

関数が入れ子になっていて処理を追いづらいですが、実際は型を変換して各桁の合計を求めているだけなので難しくはないです。

ABC088B - Card Game for Two

解法：入力された数字を降順に並び替えて Alice は奇数番目の数字を、Bob は偶数番目の数字を合計して、二人の差を求める。

# コード
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

# 入力
5
4 19 2 8 16

# 出力
9

--- コード解説 ---

n = int(input())

input() で標準入力から '5' を取得する。

int('5') でキャストして 5 にする。

n に 5 を代入する。

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

input().split() で標準入力から ['4', '19', '2', '8', '16'] を取得する。

map(int, ['4', '19', '2', '8', '16']) でキャストして [4, 19, 2, 8, 16] にする。

list([4, 19, 2, 8, 16]) でイテレータをリストにする。

sorted([4, 19, 2, 8, 16], reverse=True) で数値を降順に並び替え [19, 16, 8, 4, 2] を得る。

sorted() 関数は括弧の中身を昇順にソートして、新しいリストを返します。reverse=True を付けることで降順にソートできます。役割が似た関数として sort() 関数がありますが、これは元のリストを入れ替えてしまうため注意が必要です。

a に [19, 16, 8, 4, 2] を代入する。

print(sum(a[::2]) - sum(a[1::2]))

a[::2] で [19, 8, 2] を、a[1::2] で [16, 4] を得る。

sum([19, 8, 2]) は 29 、sum([16, 4]) は 20 。

print(29 - 20) で 9 を標準出力する。

--- コード解説終わり ---

Python ではスライス ([::2]) を使うことで、n 個おきに要素を取得したりできるので便利です。

ABC085B - Kagami Mochi

解法：入力された数字を取得していき、同じ数字を取得した場合はスルーすることで問題を解くことができます。

# コード
n = int(input())
print(len(set(map(int, [input() for i in range(n)]))))

# 出力
3

--- コード解説 ---

n = int(input())

input() で標準入力から '4' を取得する。

int('4') でキャストして 4 にする。

n に 4 を代入する。

print(len(set(map(int, [input() for i in range(n)]))))

input() for i in range(4) で input() を 4 回繰り返して ['10', '8', '8', '6'] を取得する。

map(int, ['10', '8', '8', '6']) でキャストして [10, 8, 8, 6] にする。

set([10, 8, 8, 6]) で同じ数値を弾いて [10, 8, 6] を得る。

len([10, 8, 6]) で [10, 8, 6] の要素数 3 を得る。

print(3) で標準出力に 3 を出力する。

--- コード解説終わり ---

ABC085C - Otoshidama

解法：お札の枚数が 1 <= N <= 2000 なので、全ての組み合わせを試して Y と一致した場合は枚数を出力してプログラムを終了し、見つからなかった場合は -1 -1 -1 を出力する。ABC087B - Coins と似たアルゴリズム。

# コード
n, y = map(int, input().split())
for i in range(n + 1):
  for j in range(n - i + 1):
    if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
      print(i, j, n - i - j)
      exit()
print("-1 -1 -1")

# 入力
9 45000

# 出力
0 9 0

--- コード解説 ---

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

input().split() で標準入力から ['9', '45000'] を取得する。

map(int, ['9', '45000']) でキャスト（型変換）して [9, 45000] にする。

n に 9 を、y に 45000 を代入する。

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

y のお札の数だけ for 文を回し、全ての組み合わせを試す。

2 重 for ループを回すと

[i, j, (n - i - j)] =

[0, 0, 9] [0, 1, 8] [0, 2, 7] [0, 3, 6] [0, 4, 5] [0, 5, 4] [0, 6, 3] [0, 7, 2] [0, 8, 1] [0, 9, 0]
[1, 0, 8] [1, 1, 7] [1, 2, 6] [1, 3, 5] [1, 4, 4] [1, 5, 3] [1, 6, 2] [1, 7, 1] [1, 8, 0]
[2, 0, 7] [2, 1, 6] [2, 2, 5] ...

の順に代入される。

[0, 9, 0] の場合 if 0 * 10000 + 9 * 5000 + 0 * 1000 == 45000: で if True: となる。

print(i, j, n - i - j) で標準出力に 0 9 0 を出力する。

exit() でループの途中でもプログラムを終了する。

print("-1 -1 -1")

全てのループを通過し、一致する組み合わせがなかった場合は print(" -1, -1, -1") で標準出力に -1 -1 -1 を出力する。

--- コード解説終わり ---

今回は一致する組み合わせを全て出力するわけではないので、一つ見つけたら exit() 関数でプログラムを終了しています。exit() が無ければ全ての組み合わせを出力することもできます。

ABC049C - 白昼夢

解法：入力された文字列から 'dream' 'dreamer' 'erase' 'eraser' と一致する箇所を消していき、何も残らなければ S =T と言える。

# コード
s = input().replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
if s:
  print("NO")
else:
  print("YES")

# 入力
dreameraser

# 出力
YES

--- コード解説 ---

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

input() で標準入力から "dreameraser" を取得する。

.replace("eraser","") で "eraser" を "" (何も入っていない) に置き換えて、"dream" にする。

.replace("erase","") では一致する物がないため何も起こらない。

.replace("dreamer","") でも一致する物がないため何も起こらない。

.replace("dream","") で "dream" を "" に置き換えて "" にする。

.replace() メソッドの順番はどれでも良いわけではなく、例えば最初に "dreamer" を "" に置き換えてしまった場合は残りが "aser" となってしまうため注意が必要。

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

if "": は if False: と同じなので else の処理へ。

print("YES") で標準出力に "YES" を出力する。

if "aser": のように if 文の条件式に何らかの文字列が入っていた場合は if True: の処理が行われる。

--- コード解説終わり ---

アルゴリズムというよりは置き換える順番が決まっていることを見抜けるかどうかが重要な問題でした。

ABC086C - Traveling

解法：

# コード
n = int(input())
for i in range(n):
  t,x,y = map(int,input().split())
  if (x + y) > t or (x + y + t) % 2:
    print("No")
    exit()
print("Yes")

# 出力
Yes

--- コード解説 ---

n = int(input())

input() で標準入力から '2' を取得する。

int('2') でキャスト（型変換）して 1 にする。

n に 2 を代入する。

for i in range(n):

for i in range(2): で 0 から 1 までループする。

  t,x,y = map(int,input().split())

input().split() で標準入力から ['3', '1', '2'] を取得する。

map(int, ['3', '1', '2']) でキャスト（型変換）して [3, 1, 2] にする。

t に 3 を、x に 1 を、y に 2 を代入する。

  if (x + y) > t or (x + y + t) % 2:
    print("No")
    exit()

if (1 + 2) > 3 or (1 + 2 + 3) % 2: は if False: と同じなので次のループへ。

(x + y) > t では t 秒後までに最短でも x + y 回は移動する必要があるため x + y の方が大きい場合は旅行プランが実行不可能。(x + y + t) % 2 では x + y + t の合計が 2 で割り切れない場合、つまり x + y と t の偶奇が異なる場合は「その場にとどまることは出来ない」という条件から通り過ぎてしまう。

if True: の場合は print("No") で標準出力に "No" を出力する。

if True: の場合は exit() でプログラムを終了する。

print("Yes")

全てのループで if 文が False だった場合は print("Yes") で標準出力に "Yes" を出力する。

--- コード解説終わり ---

AtCoder を初めて挑戦する人向けに、 Python の関数の返り値から徹底的に解説しました。わかりにくい表現や間違っている箇所があれば教えていただけると幸いです。

わかりやすかったと感じた方は「スキ」ボタンを押していただけるとモチベーションに繋がります。

また、下記のボタンから私をサポートすることが出来ます。100 円から応援する事が出来るので、記事を書き続けて欲しいと思った方はサポートのほうもよろしくお願いします。

それでは最後まで読んでいただきありがとうございました。

サポートは書籍購入や記事を書く際の素材費として使わさせていただきます！

AtCoder Beginners Selection 徹底解説 【Python】

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

AtCoder Beginners Selection 徹底解説【Python】