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(N²) のアルゴリズムで順方向でねじ伏せていたのか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')