AtCoder Beginner Contest 125感想戦

AtCoder

コンテストやったきりで復習しないマンなので，
blogに書くことによって強制的に復習するライフハック()を実践していく．

AtCoder Beginner Contest 125

atcoder.jp

A - Biscuit Generator

https://atcoder.jp/contests/abc125/tasks/abc125_a

解けた．

A, B, T = map(int, input().split())
print(int((T+0.5)//A*B))

まあ，書かれていた通りに実装．
特に何もなかった．

B - Resale

https://atcoder.jp/contests/abc125/tasks/abc125_b

解けた．

import numpy as np
N = int(input())
V = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))
ans = 0
for i in V-C:
    if(i > 0):
        ans += i
print(ans)

最初読んだ時に，何にもわからん.....DPとか要るんか？？？？
ってなって絶望しかけた．
B問題で要るはずがないと思って考えたら，
価値-コストが正のものだけ選べばということに気づいてAC．
行列同士の引き算とかする時は，本当にNumPyが便利．

C - GCD on Blackboard

https://atcoder.jp/contests/abc125/tasks/abc125_c

解けなかった....
頭ワルワルTLE実装

from functools import reduce

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def gcd_list(numbers):
    return reduce(gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

max_ans = 0
for i in range(len(A)):
    tmp = A[:i] + A[1+i:]
    ans = gcd_list(tmp)
    if max_ans < ans:
        max_ans = ans
print(max_ans)

一個を除いた場合の最大公約数なのはわかるけど，
時間を短くする方法を思いつかなかったorz
あと，AtCoderのPythonのバージョンが3.4なので，
最大公約数を求めるgcdはmathモジュールじゃなくて，
fractionsモジュールにあるのを初めて知った．

Twitterで観測した解法は，

  • 累積最大公約数
  • 数列のテキトーな2要素(1個目と2個目とか)の約数の和集合を取って全探索

の2種類があった気がする．
2つ目の解き方もあー，言われてみればと思ったけど，
今回は1つ目の解き方でお直しした．

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a


N = int(input())
A = list(map(int, input().split()))

# 累積最大公約数的な
head = []
tail = []
head.append(A[0])
tail.append(A[-1])
for i, j in zip(A[1:], A[N-2::-1]):
    head.append(gcd(head[-1], i))
    tail.append(gcd(tail[-1], j))
ans = 0
for i in range(len(head)-2):
    tmp = gcd(head[i], tail[len(tail)-1-2-i])
    if ans < tmp:
        ans = tmp
print(max(head[-1], head[-2], tail[-2], ans))

D - Flipping Signs

https://atcoder.jp/contests/abc125/tasks/abc125_d

解けた．

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))

ans = np.zeros(1, dtype=np.uint64)
even_odd = 0
mini = 1000000000

for i in A:
    if(i < 0):
        even_odd = (even_odd + 1) % 2
    ans += abs(i)
    if(mini > abs(i)):
        mini = abs(i)
        
if(even_odd == 0):
    print(ans[0])
else:
    print((ans - (mini * 2))[0])

D問題だし，やっぱ難しいな～と思って紙に書いてたら，
あれ，これ結局マイナスを自由に移動できるから，
最終的に負の数が0か1にしかならないじゃんって気づけた．

結果

result
result