AtCoder Beginner Contest 125

A - Biscuit Generator

A秒間隔でB個のビスケットを生産する装置がある時に、T+0.5秒ごに生産されるビスケットの総数を求める問題。

T+0.5の制約は、T秒に生産されたものも数えるという意味
生産されるのは、A秒、2A秒、3A秒(スタート時点では生産されない)

解法

秒数がT+0.5を越えるまでループして加算すれば良い

# A
a, b, t = map(int, input().split())

count = a
ans = 0
while True:
    if count > t + 0.5:
        break
    count += a
    ans += b
print(ans)

B - Resale

N個の宝石があり、i番目価値がViで購入にかかるコストがCiである。この時、合計価値-合計コストの最大値を求める問題。

解法

価値-コストが最大になるものを全て選び、それらのプラス分を加算して行く問題

# B
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = 0
for i in range(n):
    gain = v[i] - c[i]
    if gain > 0:
        ans += gain
print(ans)

C - GCD on Blackboard

N個の整数があり、一つを好きな整数に書き換えることができる時、それらの整数の最大公約数の最大値を求める問題。

最大公約数を求める問題なので、書き換える部分は「消す」という処理に置き換えることができる。
i番目以外のN-1個のgcdを計算すると、O(N²)となり、間に合わない。

解法

最大公約数を左右からそれぞれ計算していく、それまでの最大公約数以上になることはないので、1つ前までの最大公約数と次の数の最大公約数のみを計算すれば良い。

# C
import functools
# 3.4以前は math の gcd が対応していないので fractions or 自作のものを使う
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)

# 入力
n = int(input())
a = list(map(int, input().split()))

# 左から一つずつ最大公約数をとるものと、右から一つずる最大公約数をとるものを作る
# O(N) + O(N)
gcd_left = [a[0]]
for i in range(1,n):
    if gcd_left[i-1] != 1:
        res = gcd(gcd_left[i-1], a[i])
    else:
        res = 1
    gcd_left.append(res)

gcd_right = [a[-1]]
for i in range(1,n):
    if gcd_right[i-1] != 1:
        res = gcd(gcd_right[i-1], a[-(i+1)])
    else:
        res = 1
    gcd_right.append(res)
gcd_right = gcd_right[::-1]

# 最大のものを探す
# O(N)
ans = 0
for i in range(n):
    if i == 0:
        res = gcd_right[1]
    elif i == n-1:
        res = gcd_left[-2]
    else:
        res = gcd(gcd_right[i+1], gcd_left[i-1])
    ans = max(res, ans)
print(ans)

D - Flipping Signs

N個の整数があり、連続する2つの整数の符号を反転させる処理を何度でも行うことができる。この時、処理後の整数の和の最大値を求める問題。

連続する2つの整数の符号を反転させることができるので、実質離れたところにある2つの整数の符号をいくらでも反転できる。
ここで重要なのは、反転させることができるのは偶数個である点である。

解法

入力された整数のうち、負のもの(0を含む)をできるだけプラスにすれば良い。
負のものが奇数個の場合、1つはマイナスが残ってしまう。
負のものが奇数個の場合は、正・負の中で絶対値が最も小さいものをマイナスにすることで合計をできるだけ大きくする。

# D
n = int(input())
a = list(map(int, input().split()))

l_minus = [i for i in a if i <= 0]
l_plus = [i for i in a if i > 0]

ans = 0
if len(l_minus) % 2 == 0:
    l_minus_edit = [-i for i in l_minus]
else:
    l_minus_edit = [-i for i in l_minus]
    temp = l_plus[:]
    temp.extend(l_minus_edit)
    l_minus_edit.append(-min(temp) * 2)

ans = sum(l_plus) + sum(l_minus_edit)
print(ans)