PythonによるAtCoder Beginners Selection - 優秀コードとの比較

最近AtCoderを始めました。
今は[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)という、優良な過去問10題をまとめた初心者向けの問題をやっています。

この記事では自分が書いた下手コードと、実行時間が短かったりなるほどと思うような素敵コードを比べてみました。

※前から3問 [ABC086A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a), [ABC081A - Placing Marbles](https://atcoder.jp/contests/abs/tasks/abc081_a), [ABC081B - Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)についてはすみません、いずれ追加します。

## [ABC087B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)
### 自分のコード
```python
A = int(input())
B = int(input())
C = int(input())
X = int(input())
out = 0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      out = out+1 if 500*a+100*b+50*c==X else out
print(out)
```
### 素敵なコード
```python
A,B,C,X = [int(input()) for i in range(4)]
X //= 50
ans = 0
for i in range(A + 1):
    if 10*i > X: break
    rem = X - 10*i
    for j in range(B + 1):
        if 2*j > rem: break
        if rem - 2*j <= C:
            ans += 1
print(ans)
```

### 比較  
|   | 実行時間 | コード長 | メモリ |
|---|---|---|---|
|自分のコード|59 ms|214 Byte|3060 KB|
|素敵なコード|17 ms|250 Byte|2940 KB|

まず標準入力から違いますね。forで回して行を減らす、うーんスマート。
続いて2行目`X //= 50`。Xが50の倍数という問題設定を利用して値を小さくしています。これも速度向上の効果があるのでしょうか。
特筆すべきはforループが自分のコードより1個少ない！確かに500円と100円の個数が決定した時点で、50円の個数も決定しますね…3倍速度差があるのはここが一番効いてそうです。

## [ABC083B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)
### 自分のコード
まず初めに思いつくだろうというのをそのまま書いた感じですね。1~Nまで確認して、条件満たしてたらtotalに加算しています。
数値の各桁の和は10で割って余りを足して…を繰り返しています。

```python
N,A,B = map(int,input().split())
total = 0
for i in range(N):
    j=i+1
    lst = []
    while j>0:
        lst.append(j%10)
        j //= 10
    total = total+i+1 if A<=sum(lst)<=B else total
print(total)
```

### 速いコード
1の各桁の和は1, 11は2, 21は3,…のような数字の規則性に目をつけて、予めN=0~10^4までの答えを用意する作戦ですね。自分も思い付きはしたもののどう実装すべきか分からなかった…
後述しますがかなり実行時間が短縮されてます。

```python
dig1 = list(range(10))
dig2 = []
print(dig1)
for i in range(10):
    dig2 += [j+i for j in dig1]
print(dig2)
dig3 = []
for i in range(10):
    dig3 += [j+i for j in dig2]
print(dig3)
dig4 = []
for i in range(10):
    dig4 += [j+i for j in dig3]
print(dig4)
dig4.append(1)

def sumup(n, a, b):
    return sum([i for i, dig in enumerate(dig4[:n+1]) if a <= dig <= b])

n, a, b = [int(x) for x in input().split()]
print(sumup(n, a, b))
```


### 短いコード
最もコード長の短いプログラムで、たった2行！発想は私のコードと同じなのに…
凄いのは`sum(map(int,str(i)))`こんなに短く各桁の和が求まるんですね。
それから`i*(A<=sum(map(int,str(i)))<=B)`この部分は数値にbool型を掛けており、`i*True=i`、`i*False=0`という性質を利用しています。
これぞ競プロって感じですよね。

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

### 比較  
|   | 実行時間 | コード長 | メモリ |
|---|---|---|---|
|自分のコード|31 ms|217 Byte|3060KB|
|速いコード|19 ms|442 Byte|3572 KB|
|短いコード|28 ms|93 Byte|3064 KB|
こう見るとそれぞれ一長一短、いや自分のは"短いコード"の下位互換ですが…~~メモリ効率は少し勝ってる~~

## [ABC088B -  Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)
### 自分のコード
AとB交互に、値が大きい要素をpopしています。

```python
N = input()
A = 0
B = 0
Cards = list(map(int,input().split()))
for i in range(-(-len(Cards)//2)):
    A += Cards.pop(Cards.index(max(Cards)))
    B = B+Cards.pop(Cards.index(max(Cards))) if len(Cards)!=0 else B
print(A-B)
```

###短いコード
まずsorted()でソートし、そのリストを1個飛ばしでスライシング。

```python
input();a=sorted(map(int,input().split()))
print(sum(a[::-2])-sum(a[-2::-2]))
```

### 比較
|   | 実行時間 | コード長 | メモリ |
|---|---|---|---|
|自分のコード|17 ms|228 Byte|3060 KB|
|短いコード|18 ms|78 Byte|2940 KB|
短いコードが1ms遅いのは一度ソートしてるからでしょうか。

## [ABC085B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)
要素の重複を除いたリストを作るだけって感じの問題で、pythonでは集合型を使えばいいので簡単でした。

### 自分のコード
一度リスト[ ]を作ってから集合型に変換しているので非効率です。

```python
N = int(input())
print(len(set([int(input()) for _ in range(N)])))
```

### 短いコード
こちらのコードは初めから集合型{}に格納していってます。

```python
print(len({input()for _ in[0]*int(input())}))
```

### 比較
|   | 実行時間 | コード長 | メモリ |
|---|---|---|---|
|自分のコード|17 ms|67 Byte|2940 KB|
|短いコード|17 ms|45 Byte|2940 KB|
意外にも実行時間は同じでした。

## [ABC085C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)
### 自分のコード(1)Reject
まずN枚全て1000円札にして、金額が足りなければ5000円と交換、まだ足りなければ10000円と交換、という風に両替していくアイデア。
半分くらいのケースでRejectされた（恐らくタイムアウト）。

```python
def getTotal(a,b,c):
    return 10*a+5*b+c

N,otoshi=map(int,input().split())
otoshi /= 1000
a,b,c = 0,0,N
while otoshi-4>=getTotal(a,b,c) and c>0:
    b+=1;c-=1
otoshi_d = list(map(int,str(int(otoshi))))
ttl_d = list(map(int,str(getTotal(a,b,c))))
while otoshi_d[len(otoshi_d)-1] != ttl_d[len(ttl_d)-1]:
    b-=1;c+=1
    ttl_d = list(map(int,str(getTotal(a,b,c))))
for i in range(b+1):
    if getTotal(a,b,c)==otoshi:
        print("{} {} {}".format(a,b,c))
        break
    if otoshi-5>=getTotal(a,b,c) and b>0:
        a+=1;b-=1
    else:
        print("-1 -1 -1")
```

### 自分のコード(2)Accept
普通にループ回せば出来るやん！と気づいて書いたコード。
10000円を一番外側にした3重…ではなく2重ループ。10000円と50000円の枚数から1000円札の数も分かるため。
恐らく何も考えず3重ループで回したらタイムアウトするようになっており、これがC問題かと思わされました。

```python
N,otoshi=map(int,input().split())
otoshi /= 1000
for a in range(N+1):
    for b in range(N+1):
        c = N - (a+b)
        if c<0:
            break
        if 10*a+5*b+c==otoshi:
            print("{} {} {}".format(a,b,c))
            exit()
print("-1 -1 -1")
```

### 速いコード

```math
\begin{cases}
n = a + b + c \\
y = 10*a + 5*b + c
\end{cases}
```
の連立方程式を解いて書いているのだと思われる。

```python
n, y = list(map(int, input().split()))
y = int(y/1000)
a = y%5
for i in range(n+1):
    if a == i%5:
        b = int((y-i)/5)
        c = n-i
        if b <= 2*c and b >= c:
            print(b-c, 2*c-b, i)
            exit()
print(-1, -1, -1)
```

### 比較
|   | 実行時間 | コード長 | メモリ |
|---|---|---|---|
|自分のコード(2)|925 ms|272 Byte|3188 KB|
|速いコード|17 ms|253 Byte|3064 KB|
自分のコードおっそいなあ…

## [ABC049C - 白昼夢 / Daydream](https://atcoder.jp/contests/abs/tasks/arc065_a)
### 自分のコード
後ろから1文字ずつ照合すると簡単に解けました。

```python
import sys
S = input()
words = ['dream','dreamer','erase','eraser']
T = ""
while True:
    for i in range(len(words)):
        if words[i] == S[-(len(words[i])):]:
            T = words[i] + T
            S = S[0:len(S)-len(words[i])]
            if(len(S)==0):
                print("YES")
                sys.exit()
            break
        elif i == len(words)-1:
            print("NO")
            sys.exit()
```

### 速いコード
これは…ずるいいやすごい。

```python
s=input().replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
print("YES" if len(s)==0 else "NO")
```

### 比較
|   | 実行時間 | コード長 | メモリ |
|---|---|---|---|
|自分のコード(2)|155 ms|431 Byte|3344 KB|
|速いコード|18 ms|131 Byte|3188 KB|
比べるまでもないですが…

## [ABC086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)
### 自分のコード
再帰関数rootでひたすら探索します。一応可能なルートが見つかったら打ち切るようにしているのですが、それでもタイムアウトしてしまいました。

```python
import sys
import os
f = open('input.txt', 'r')
sys.stdin = f

now = [0,0,0]
def root(now_,purpose):
    if now_==purpose:
        global now
        now = purpose
        return
    elif(now_[0]<=purpose[0] and now!=purpose):
        root([now_[0]+1,now_[1]+1,now_[2]],purpose)
        root([now_[0]+1,now_[1]-1,now_[2]],purpose)
        root([now_[0]+1,now_[1],now_[2]+1],purpose)
        root([now_[0]+1,now_[1],now_[2]-1],purpose)
    return

N = int(input())
for i in range(N):
    purpose = list(map(int,input().split()))
    root(now,purpose)
    if now!=purpose:
        print("No")
        sys.exit()
if now==purpose:
    print("Yes")
```
### 速いコード
とてもシンプル。**コード中のif文の条件を満たさなければ必ず辿り着ける**というルールに気付くかどうかの問題だったようです。

```python
from sys import stdin
 
n = int(stdin.readline())
for i in range(n):
    t, x, y = map(int, stdin.readline().split())
    dist = x + y
    if t < dist or (dist % 2) != (t % 2):
        print("No")
        exit()
 
print("Yes")
```

## 感想
C問題を解いてて思ったのは、このレベルではアルゴリズムを駆使して複雑な問題を解く能力というより、柔軟な発想で規則性に気づけるかが問われているということ。
それが分かっただけでも大きな収穫でした。