概要

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

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

参考:

AtCoder Beginners Selection: 10題
- 解説Qiita記事: AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～
私の環境構築: WSL で AtCoder 用の環境(Python3)を整える

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*Trueは7 で7*Falseは0という言語仕様を押さえると、内包表現における 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$で距離の判定をしなければいけないとされていたが、このコードではそれを怠っている。