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

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

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

参考:

- [AtCoder Beginners Selection](https://atcoder.jp/contests/abs): 10題
   - 解説Qiita記事: [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)
- 私の環境構築: [WSL で AtCoder 用の環境(Python3)を整える](https://qiita.com/41semicolon/items/b4e7904395797085a9bd)


### 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$で距離の判定をしなければいけないとされていたが、このコードではそれを怠っている。