この記事では、AtCoder Beginners Selection 10+1問にPython (3.8) で解答を与えます。
AtCoder Beginners Selectionとは
AtCoderは日本発の競技プログラミングサービスです。詳細については、@drkenさんや@e869120さんの記事
などをご覧下さい。とくに、@drkenさんが
でまとめた過去問10問を、のちにAtCoder公式がAtCoder Beginners Selectionと名付けて初心者用の練習問題として採用しました。
参考文献
AtCoder Beginners SelectionのPythonによる解答は既にいくつかありますが、この記事はとくに参考にさせて頂きました。ありがとうございます。この記事では、自分なりにより"良い"と感じる解答を与えます。見比べて頂ければ、細かく改善してあるのが見てもらえるかと思います。
良いコードとは
余談ですが、コードの"良さ"は目的や状況次第であって明確に定義できる概念ではないとは思うものの、主に
- 人間側の事情：可読性
- 機械側の事情：時間計算量、空間計算量
の２方向があり、この２方向の間にはしばしばトレードオフが生じるように思います。このトレードオフはコードを書く以前に言語選択の時点でも現れており、この記事のようなPythonによる解答とdrkenさんのC++による解答を比べてみても分かるように、C++に比べてPythonで書くという選択は計算量を犠牲にして可読性を優先する立場を取っているように思われます。
コードの"良さ"としては簡潔さもよく挙げられますが、使い捨てのコードでは無い限り、簡潔さは可読性に寄与するときのみ価値があり、可読性が下がる場合はコードを短くしないほうが良いのではないかと個人的には思います。
解答
0. PracticeA - Welcome to AtCoder
a = int(input())
b, c = map(int, input().split())
s = input()
print(a+b+c, s)
1. ABC086A - Product
a, b = map(int, input().split())
print("Odd" if a%2 and b%2 else "Even")
-
a%2 and b%2は問題文どおりに(a*b) % 2でもよい
2. ABC081A - Placing Marbles
print(input().count("1"))
3. ABC081B - Shift only
_ = input()
A = [*map(int, input().split())]
count = 0
while not any(a%2 for a in A):
A = [a/2 for a in A]
count += 1
print(count)
-
a%2でaが奇数かどうか、any(a%2 for a in A)でAに奇数が含まれているかどうかというboolを表せる。0以外の数はTrueと解釈されるのでanyはsumでもよく、なぜかsumのほうが速かったが、可読性のためにanyにした - 問題文どおりに解くとこう。2進法で右に何個0が続くかを読み取るなどして各数が何回2で割れるかを数えていく方法もある
4. ABC087B - Coins
import itertools as it
A, B, C, X = map(int, [input() for _ in range(4)])
count = 0
for a, b, c in it.product(range(A+1), range(B+1), range(C+1)):
if 500*a + 100*b + 50*c == X:
count += 1
print(count)
- 全探索の計算量は $O(50^3)$ で、 $O(100^3)=O(10^6)$ と大きめに見積もっても時間計算量上限の目安 $O(10^8)$ を大きく下回っているので、全探索で大丈夫
-
for文のネストはitertools.productで書きなおすと読みやすいと思う
5. ABC083B - Some Sums
N, A, B = map(int, input().split())
print(sum(i for i in range(N+1) if A <= sum(map(int,str(i))) <= B))
-
intのiに対し、str(i)にintをmapすれば、iの各桁のintが入った配列が手に入る
6. ABC088B - Card Game for Two
_ = input()
a = sorted(map(int,input().split()), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))
- 全カードをソートして、偶数番の和から奇数番の和を引けばよい
7. ABC085B - Kagami Mochi
N = int(input())
print(len(set(input() for _ in range(N))))
8. ABC085C - Otoshidama
N, Y = map(int, 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)
exit()
print(-1, -1, -1)
-
n_10k,n_5k,n_1kがそれぞれ1万円札、5千円札、千円札の枚数を表している - この3変数の合計値が
Nという拘束のおかげで、探索は実質2変数で済む。全探索は計算量が$O(2000^2)=O(8\times 10^6)$であり計算量上限の目安$O(10^8)$を下回るので、全探索で大丈夫 - ネストした
forループを途中で終了したいとき、breakで抜けようとすると少しトリッキーなコードになるので、このようにexit()でプログラムを終了してしまうのもありかと思う
9. ABC049C - 白昼夢
S = input()
while S:
for x in ["dream","dreamer","erase","eraser"]:
if S.endswith(x):
S = S[:-len(x)]
break
else:
print("NO")
break
else:
print("YES")
- 接頭語がどれであるかは一意に定まらないけれど、接尾語がどれであるかなら一意に定まる
-
for ... else ...やwhile ... else ...のelseは、forやwhileが正常終了した場合に作動し、breakで異常終了した場合には作動しない
10. ABC086C - Traveling
t0, x0, y0 = 0, 0, 0
for _ in range(int(input())):
t, x, y = map(int, input().split())
margin = (t-t0) - abs(x-x0) - abs(y-y0)
if margin < 0 or margin%2 != 0:
print("No")
break
t0, x0, y0 = t, x, y
else:
print("Yes")
- まず、
marginが負だと目的の点に辿り着けない。さらに、静止する選択肢が無いためmarginが奇数だと目的の点に居ることができない - 全ての
(t,x,y)を受け取ってから一括処理するバッチ版のコードではなく、このように各(t,x,y)を逐次的に処理するオンライン版のコードにできる