「AtCoder Beginners Selection」のPythonの解説です。
AtCoder Beginners Selection とは？
「AtCoder Beginners Selection」とは、「AtCoderに登録したけど何をしていいか分からない・・・！」という人に向けて作られた、初心者向け問題集[1]です。
AtCoderの使い方を確認できる「PracticeA – Welcome to AtCoder」と基本的な問題10個が用意されています。
Atcoder初心者の方の最初の目標である「Cランクの問題」まで一通り体験できるため、是非一度挑戦してみてください。
PracticeA – Welcome to AtCoder
AtCoderはデータが与えられ、それをまず「入力」する必要があります。
問題の形式によって、その都度変更しなければなりませんが、以下が基本的な形となります。
# 入力
a = int(input()) # 数値の入力
b, c = map(int, input().split()) # mapは配列の各要素に関数を適応する。今回のように、型変更にも使える。
s = input() # 文字列の入力
# 出力
print(f"{a+b+c} {s}") # f文字列出力で使用している「f文字列」は文字列に変数を直接埋め込むことができるので、便利です。
A問題
ABC086A – Product
偶数と奇数を判定するには%を使うのが一般的です。
# 入力
a, b = map(int, input().split())
# 処理
if (a*b)%2 == 0:
s = "Even"
else:
s = "Odd"
# 出力
print(f"{s}")ABC081A – Placing Marbles
文字列を1文字ずつ配列に格納するには、list(文字列)とします。
# 入力
a,b,c = map(int,list(input()))
# 出力
print(f"{a+b+c}")B問題
ABC081B – Shift only
# 入力
N = int(input())
A = [int(i) for i in input().split()]
# 処理
Answer = 0
loop = True
while True:
for i in range(N):
if A[i]%2 == 0:
A[i] = (A[i]/2)
else:
loop = False
if loop:
Answer += 1
else:
break
# 出力
print(f"{Answer}")ABC087B – Coins
一見数学的に考えたくなりますが、シンプルな全探索で全パターン調べられます。つまり、ネストしてfor文を回すだけです。
# 入力
A = int(input())
B = int(input())
C = int(input())
X = int(input())
# 処理
ans = 0
for a in range(A+1):
for b in range(B+1):
for c in range(C+1):
total = 500*a+100*b+50*c
if total == X:
ans += 1
# 出力
print(f"{ans}")ABC083B – Some Sums
方法は二種類あります。
- 文字列に変換し、
list(文字列)で桁ごとに分割した後、それぞれを数値に変換して足す - 10で割った余りを足したのち、切り捨て除算で更新する
# 入力
N,A,B = map(int, input().split())
# 処理
# def com(x): # 文字列にして愚直に足した
# sum = 0
# for i in list(str(x)):
# sum += int(i)
# return sum
def com(x): # 10で割った余りを足した
sum = 0
while x > 0:
sum += (x % 10)
x //= 10 # 切り捨て除算
return sum
sum = 0
for i in range(N+1):
if A <= com(i) <= B:
sum += i
# 出力
print(f"{sum}")ABC088B – Card Game for Two
この問題はソートが鍵となります。
# 入力
N = int(input())
a = list(int(i) for i in input().split())
# 処理
a = sorted(a,reverse=True)
Alice = 0
Bob = 0
turn = "Alice"
for i in a:
if turn == "Alice":
Alice += i
turn = "Bob"
else:
Bob += i
turn = "Alice"
# 出力
print(f"{Alice - Bob}")ABC085B – Kagami Mochi
この問題もシンプルなソート問題です。
# 入力
N = int(input())
a = [int(input()) for i in range(N)] # N回繰り返し配列
# 処理
a = sorted(a)
mochi = 0
before = 0
for i in a:
if i > before:
mochi += 1
before = i
# 出力
print(f"{mochi}")C問題
ABC085C – Otoshidama
先ほどの全探索問題と同じかと思われますが、Cもループすると(N+1)^3となり、最大2000^3=8,000,000,000で「80億回」ループすることになります。
1秒間で処理できるfor文のループは1億回(10^8)程度[2]なので、とてもじゃないですが時間が足りません。テストは2秒以内に収める必要があります。
そこで、cのループを除外します。cはaとbが決まれば自動で決まるので省略できます。すると(N+1)^2となり、最大値も2000^2=8,000,000となって問題が解決します。
# 入力
N, Y = map(int, input().split())
# 処理
def solve(N,Y):
for a in range(N+1):
for b in range(N+1):
# Cのループもいれると、(N+1)^3となる。これだと時間がかかりすぎるので、Cのループを削除して、(N+1)^2にする。
c = N - (a + b)
if c >=0 and 10000*a+5000*b+1000*c == Y:
return f"{a} {b} {c}"
return "-1 -1 -1"
# 出力
print(solve(N,Y))ABC049C – 白昼夢
この問題は文字列を逆さまにすると簡単に解けます。
「dreamとdreamer」「eraseとeraser」で、それぞれどちらを適用すべきか判断できない点が難しいのですが、これを逆さまにすると、「maerd、remaerd、resare、esare」と共有部分が無くなるため悩む点が無くなります。
このような被っている関係を「prefix」と呼ぶそうです。
あとは、パターンマッチには正規表現を使用しましょう。
# 入力
S = input() # 文字列の入力
# 処理
import re
def solve(pattern,S):
S = S[::-1]
while S != "":
if re.match(pattern,S[:5]) != None:
S = S[5:]
elif re.match(pattern,S[:6]) != None:
S = S[6:]
elif re.match(pattern,S[:7]) != None:
S = S[7:]
else:
return "NO"
return "YES"
# 出力
pattern = r"(maerd|remaerd|resare|esare)"
print(solve(pattern,S))ABC086C – Traveling
この問題は「時刻tが偶数なら、x+yも偶数である」「時刻tが奇数なら、x+yも奇数である」というルールに気付けるかどうかだけです。
このような偶奇に関する性質を「パリティ」と呼ぶそうです。
# 入力
N = int(input())
p = [list(map(int, input().split())) for i in range(N)]
# 処理
def solve(N,p):
start = [0,0,0]
for i in range(N):
dt = abs(p[i][0]-start[0])
dist = abs(p[i][1]-start[1])+abs(p[i][2]-start[2])
start[0] = p[i][0]
start[1] = p[i][1]
start[2] = p[i][2]
if dist > dt:
return "No"
if dt % 2 == 0 and dist % 2 != 0:
return "No"
elif dt % 2 != 0 and dist % 2 == 0:
return "No"
return "Yes"
# 出力
print(solve(N,p))まとめ
AtCoderでまず最初にやるべき「AtCoder Beginners Selection」を解説しました。
A問題、B問題は特に問題なく解けましたが、C問題は骨が折れました。とてもAtCoderらしい問題だと思います。
「AtCoder Beginners Selection」を終えた後は、毎週土曜日21時開催の「AtCoder Beginner Contest」(通称:ABC)に挑戦してみてください。
