Python3によるAtCoder Beginners Selectionの解答

この記事では、AtCoder Beginners Selection 10+1問にPython (3.8) で解答を与えます。

### **AtCoder Beginners Selectionとは**
[AtCoder](https://atcoder.jp/)は日本発の競技プログラミングサービスです。詳細については、@drkenさんや@e869120さんの記事

- [AtCoder コンテストについての tips](https://qiita.com/drken/items/8a6f139158cde8a61dce)
- [レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】](https://qiita.com/e869120/items/f1c6f98364d1443148b3)

などをご覧下さい。とくに、@drkenさんが

- [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](
https://qiita.com/drken/items/fd4e5e3630d0f5859067)

でまとめた過去問10問を、のちにAtCoder公式が[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)と名付けて初心者用の練習問題として採用しました。

### 参考文献
- [AtCoder に登録したら解くべき精選過去問 10 問 をPythonで解いてみた](http://delta114514.hatenablog.jp/entry/2018/03/15/014555)

AtCoder Beginners SelectionのPythonによる解答は既にいくつかありますが、この記事はとくに参考にさせて頂きました。ありがとうございます。この記事では、自分なりにより"良い"と感じる解答を与えます。見比べて頂ければ、細かく改善してあるのが見てもらえるかと思います。


### **良いコードとは**

余談ですが、コードの"良さ"は目的や状況次第であって明確に定義できる概念ではないとは思うものの、主に

- 人間側の事情：可読性
- 機械側の事情：時間計算量、空間計算量

の２方向があり、この２方向の間にはしばしばトレードオフが生じるように思います。このトレードオフはコードを書く以前に言語選択の時点でも現れており、この記事のようなPythonによる解答とdrkenさんのC++による解答を比べてみても分かるように、C++に比べてPythonで書くという選択は計算量を犠牲にして可読性を優先する立場を取っているように思われます。

コードの"良さ"としては簡潔さもよく挙げられますが、使い捨てのコードでは無い限り、簡潔さは可読性に寄与するときのみ価値があり、可読性が下がる場合はコードを短くしないほうが良いのではないかと個人的には思います。

# **解答**

#### 0. PracticeA - Welcome to AtCoder
```py
a = int(input())
b, c = map(int, input().split())
s = input()

print(a+b+c, s)
```


#### 1. ABC086A - Product
```py
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
```py
print(input().count("1"))
```


#### 3. ABC081B - Shift only
```py
_ = 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
```py
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
```py
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
```py
_ = input()
a = sorted(map(int,input().split()), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))
```
- 全カードをソートして、偶数番の和から奇数番の和を引けばよい

#### 7. ABC085B - Kagami Mochi
```py
N = int(input())
print(len(set(input() for _ in range(N))))
```


#### 8. ABC085C - Otoshidama
```py
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 - 白昼夢
```py
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
```py
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)`を逐次的に処理するオンライン版のコードにできる