Posted at

AtCoder 最初にやる10題の熟練コードを読む(Python3)


概要

AtCoder に登録した直後のチュートリアル10題をやった。問題は簡単なので他の人の短いコードを読み、有用そうなものをまとめた(評価基準は最短のコードというわけではないがTOP20以内)。

コード引用のファイル名が submission番号。

参考:


1. 偶数判定

二つの数字のどちらか一方でも偶数であるかを判定(ABC086A)


2206205.py

print(['Even','Odd'][eval(input().replace(' ','*'))%2])


概説: 入力文字列 10 4のスペースを*にすると10*4になる。それを eval した結果を 2 で割った余りを インデックス番号として利用する。


2. 特定文字のカウント

文字列に含まれる1の数をカウント(ABC081A):


4778576.py

print(input().count("1"))


概説: 説明不要


3. 何回シフト可能?

N個の数が与えられたとき、それら全てを割り切る $2^m$ の形の最大の整数$m$は?(ABC081B):


3957562.py

input()

a = [bin(int(s))[::-1].find("1") for s in input().split()]
print(min(a))

概説: 自然数 M が何回2で割れるかどうかは binで 2進文字列に直したとき後ろから探索して最初に 1 が出てきたインデックスでわかる(例: 0b101100の場合 後ろから数えて2番目に1があるので 2回 2で割れる)。与えられた全ての数でやってその最小値が答えになる。


4091981.py

input()

N = eval(input().replace(" ","|"))
print(bin(N)[::-1].find("1"))

概説: 与えられた数を全部 ビットOR した数 Nを作る。この N に対してあるビットが 0 であることは何を意味するだろうか?それは与えられた数全てについて そのビットが立っていなかったことを示す。逆に 1 であった場合は 与えられた数のどれかがそのビットが立っていたことを示す。したがって、Nの2進表記を後ろから見て 1 が見つかった場所が答えになるとわかる。


4. X円をコインで払う

500,100,50の3種類のコインで与えられた額を払う方法は何通り?ただしコイン各種に使ってよい上限値が存在(ABC087B)


2422546.py

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

print(sum(1 for i in range(a + 1) for j in range(b + 1) if 0 <= (x - (i * 500 + j * 100)) // 50 <= c))

概説: 500,100の2種類のコインの上限値を使った if付きの2重の内包表記を利用。if をパスしたら 1を割り当てるので、sumすれば何通りかがわかる。500と100のコインの使用枚数が与えられたら 50 のコインをどうするか(ちゃんと払えるかも含めて)一意にきまるので3重ループにする必要がない。


5. 各桁の総和

自然数$N$, 区間$[a, b]$を与える。$1,2....,N$のそれぞれの数について、その10進表記における桁の総和が$[a, b]$に入っているものを抽出して総和をもとめよ(ABC083B)


2590067.py

N,A,B=map(int,input().split())

print(sum(i*(A<=sum(map(int,str(i)))<=B)for i in range(N+1)))

概説: 説明不要。7*True77*False0という言語仕様を押さえると、内包表現における if が不要になる。


6. 和を求めよ

与えられた配列を降順にソートして偶数番目の和と奇数番目の和の差を求めよ(ABC088B)


4824436.py

input()

n=sorted(map(int,input().split()))
print(sum(n[-1::-2])-sum(n[-2::-2]))

概説: reverse=Trueをしないので逆順で巡る


7. 異なる要素数

distinct な要素数をもとめよ(ABC085B):


2519150.py

print(len({input() for i in range(int(input()))}))


概説: 説明不要


8. つるかめ算(お札)

お札は3種類(10000,5000,1000)。お札の総枚数 $N$と 合計金額 $Y$ を与える。それが可能ならば例を一つ挙げよ(ABC085C)


4202917.py

r=range

n,y=map(int,input().split())
for i in r(n+1):
for j in r(n+1-i):
if i*10000+j*5000+(n-i-j)*1000==y:print(i,j,n-i-j);exit()
print(-1,-1,-1)

概説: 10000と5000の枚数で二重ループ。両者が決まれば 1000の枚数は計算できる。


3910642.py

N,S=map(int,input().split())

S/=1000
L=S-N
for x in range(int(L/9),-1,-1):
y=(L-9*x)/4
if y.is_integer() and N>=x+y:
exit(print(x,int(y),int(N-x-y)))
else:
print("-1 -1 -1")

概説: 若干長いけど10倍速い。枚数の方程式として $x+y+z=n$, 金額の方程式として1000で正規化すると $10x+5y+z=s$。よって $y=((s-n)-9x) / 4$ と決まるためループは 1重で済む。


9. 文字列は4つの単語のみで構成されるか?

与えられた文字列が dream, dreamer, erase, eraser の4単語を重複を許して連結したものであるかを判定せよ(ABC049C)


4761715.py

import re;print('YES'if re.search('^(eraser?|dream(er)?)*$',input())else'NO')


概説: 説明不要


4874789.py

import re

print("YES" if re.match("^(dream|dreamer|erase|eraser)+$",input()) else "NO")


10. 1歩ずつ格子を進む

2次元平面を t=0 x=y=0 からスタートし, 1秒ごとに 上下左右の格子に飛び移ってよい。$t, x, y$ をt の昇順に与えるときに、一連の移動が可能であるかを判定せよ(ABC086C)


5249498.py

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

概要: 二つの制約がある。一つはマンハッタン距離を考慮して遠すぎないか(x+y)>t?もう一つは移動に伴う不変量(パリティ)が変なことになっていないか(x+y+t)%2。「ロジックが間違っているけれど、テストケースが甘いのでACとなっている」と思われる・・・上述の解説記事でも $\Delta t, \Delta x, \Delta y$で距離の判定をしなければいけないとされていたが、このコードではそれを怠っている。