AtCoder Beginners Selection 体験記 (2回目)
AtCoder Beginners Selection 体験記 のコードが Python 2 でもう動かないので、どれくらいレベルアップしたかを確認する意味でもう一度解いてみた.
PracticeA - Welcome to AtCoder
8分→2分. スペース区切りの文字列を % で生成していたのが、print にカンマ区切りで渡せばスペース区切りで出るよと分かってそこが変わった.
a = int(raw_input())
b, c = [int(e) for e in raw_input().split()]
s = raw_input()
print "%d %s" % (a + b + c, s)
↓
a = int(input())
b, c = map(int, input().split())
s = input()
print(a + b + c, s)
ABC086A - Product
2分→1分. Odd と Even の順序が逆転した.
a, b = [int(e) for e in raw_input().split()]
if a * b % 2 == 0:
print 'Even'
else:
print 'Odd'
↓
a, b = map(int, input().split())
if a * b % 2 == 1:
print('Odd')
else:
print('Even')
ABC081A - Placing Marbles
4分→30秒. 当時は count を知らなかったようだ.
print len([c for c in raw_input() if c == '1'])
↓
s = input()
print(s.count('1'))
ABC081B - Shift only
9分→3分半. open(0).read() による一発読み込み登場. 1個づつ処理するのと、全部1回割れるのかのチェックを繰り返すのと、方針が大きく異なった.
n = int(raw_input())
a = [int(e) for e in raw_input().split()]
i = 0
while True:
if any(e % 2 == 1 for e in a):
break
i += 1
a = [e / 2 for e in a]
print i
↓
N, *A = map(int, open(0).read().split())
result = float('inf')
for a in A:
t = 0
while a % 2 == 0:
t += 1
a //= 2
result = min(result, t)
print(result)
ABC087B - Coins
4分→2分. 総当り、まあ大差ないですね.
a = int(raw_input())
b = int(raw_input())
c = int(raw_input())
x = int(raw_input())
result = 0
for i in range(a + 1):
for j in range(b + 1):
for k in range(c + 1):
if i * 500 + j * 100 + k * 50 == x:
result += 1
print result
↓
A, B, C, X = map(int, open(0).read().split())
result = 0
for a in range(A + 1):
for b in range(B + 1):
for c in range(C + 1):
if X == 500 * a + 100 * b + 50 * c:
result += 1
print(result)
ABC083B - Some Sums
6分→3分. 各桁の和を直接求めるか、文字列に変換して求めるか、方針が異なった.
n, a, b = [int(e) for e in raw_input().split()]
result = 0
for i in range(1, n + 1):
if a <= sum(int(e) for e in str(i)) <= b:
result += i
print result
↓
N, A, B = map(int, input().split())
result = 0
for i in range(1, N + 1):
c = 0
t = i
while t != 0:
c += t % 10
t //= 10
if A <= c <= B:
result += i
print(result)
ABC088B - Card Game for Two
7分→1分半. 方針はほぼ同じだが、sort の reverse オプションを当時は知らなかったようだ.
n = int(raw_input())
a = [int(e) for e in raw_input().split()]
a.sort()
a.reverse()
print sum(a[::2]) - sum(a[1::2])
↓
N, *a = map(int, open(0).read().split())
a.sort(reverse=True)
print(sum(a[::2]) - sum(a[1::2]))
ABC085B - Kagami Mochi
3分→1分半. これは覚えてた.
n = int(raw_input())
d = [int(raw_input()) for i in range(n)]
print len(set(d))
↓
N, *d = map(int, open(0).read().split())
print(len(set(d)))
ABC085C - Otoshidama
7分→3分. まあ、総当たりなので方針としては大差ない. print の使い方だけ変わった.
import sys
n, y = [int(e) for e in raw_input().split()]
for i in range(n + 1):
for j in range(n + 1 - i):
k = n - i - j
if 10000 * i + 5000 * j + 1000 * k == y:
print "%d %d %d" % (i, j, k)
sys.exit()
print "-1 -1 -1"
↓
N, Y = map(int, input().split())
for i in range(N + 1):
for j in range(N + 1 - i):
k = N - i - j
if 10000 * i + 5000 * j + 1000 * k == Y:
print(i, j, k)
exit()
print(-1, -1, -1)
ABC049C - 白昼夢 / Daydream
1時間くらい→12分. 反転すればいいというのは覚えていた. しかし、前回は O(N2) のアルゴリズムで順方向でねじ伏せていたのかw. 1223ms → 41ms と爆速化した.
import sys
s = raw_input()
ts = ['']
while True:
nts= []
for t in ts:
for w in ['dreamer', 'eraser', 'dream', 'erase']:
if s == t + w:
print 'YES'
sys.exit()
if s.startswith(t + w):
nts.append(t + w)
if len(nts) == 0:
print 'NO'
sys.exit()
ts = nts
↓
S = input()
S = S[::-1]
candidates = [s[::-1] for s in ['dream', 'dreamer', 'erase', 'eraser']]
i = 0
while i < len(S):
for c in candidates:
if S.startswith(c, i):
i += len(c)
break
else:
print('NO')
exit()
print('YES')
ABC086C - Traveling
40分くらい→8分半. バッファド IO に切り替えたので 337ms → 131ms. やってることはだいたい同じだけど、最初に入力をまとめて処理をするかしないかが違うせいでコードはだいぶ変わった.
import sys
n = int(raw_input())
data = [map(int, raw_input().split()) for i in range(n)]
t = 0
x = 0
y = 0
for d in data:
duration = d[0] - t
distance = abs(x - d[1]) + abs(y - d[2])
if (distance > duration) or ((duration - distance) % 2 == 1):
print 'No'
sys.exit()
t = d[0]
x = d[1]
y = d[2]
print 'Yes'
↓
from sys import stdin
readline = stdin.readline
N = int(readline())
pt, px, py = 0, 0, 0
for _ in range(N):
t, x, y = map(int, readline().split())
d = abs(x - px) + abs(y - py)
if d > t - pt:
print('No')
break
if (t - pt - d) % 2 == 1:
print('No')
break
pt, px, py = t, x, y
else:
print('Yes')