Go to Qiita Advent Calendar 2024 Top
LoginSignup
23
19

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@fury00812

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

Last updated at Posted at 2019-05-30

最近AtCoderを始めました。
今はAtCoder Beginners Selectionという、優良な過去問10題をまとめた初心者向けの問題をやっています。

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

※前から3問 ABC086A - Product, ABC081A - Placing Marbles, ABC081B - Shift onlyについてはすみません、いずれ追加します。

ABC087B - Coins

自分のコード

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)

素敵なコード

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

自分のコード

まず初めに思いつくだろうというのをそのまま書いた感じですね。1~Nまで確認して、条件満たしてたらtotalに加算しています。
数値の各桁の和は10で割って余りを足して…を繰り返しています。

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までの答えを用意する作戦ですね。自分も思い付きはしたもののどう実装すべきか分からなかった…
後述しますがかなり実行時間が短縮されてます。

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という性質を利用しています。
これぞ競プロって感じですよね。

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

自分のコード

AとB交互に、値が大きい要素をpopしています。

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個飛ばしでスライシング。

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

要素の重複を除いたリストを作るだけって感じの問題で、pythonでは集合型を使えばいいので簡単でした。

自分のコード

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

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

短いコード

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

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

比較

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

ABC085C - Otoshidama

自分のコード(1)Reject

まずN枚全て1000円札にして、金額が足りなければ5000円と交換、まだ足りなければ10000円と交換、という風に両替していくアイデア。
半分くらいのケースでRejectされた（恐らくタイムアウト）。

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問題かと思わされました。

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

速いコード

\begin{cases}
n = a + b + c \\
y = 10*a + 5*b + c
\end{cases}

の連立方程式を解いて書いているのだと思われる。

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

自分のコード

後ろから1文字ずつ照合すると簡単に解けました。

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

速いコード

これは…ずるいいやすごい。

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

自分のコード

再帰関数rootでひたすら探索します。一応可能なルートが見つかったら打ち切るようにしているのですが、それでもタイムアウトしてしまいました。

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文の条件を満たさなければ必ず辿り着けるというルールに気付くかどうかの問題だったようです。

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

23
19
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
23
19

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?