u++の備忘録

AtCoder Beginner Contest 125をPythonで解く

競プロ python

atcoder.jp

A - Biscuit Generator（100点）

  • Tまでに何回ビスケットが生産されるか考える
  • 0.5は無視で良い
A, B, T = list(map(int, input().split()))

ans = T//A * B
print(ans)

B - Resale（200点）

  • それぞれの宝石の「価値-コスト」を考え、正の宝石の値を合計する
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

diff = [v-c if (v-c > 0) else 0 for v, c in zip(V, C)]
print(sum(diff))

C - Unification（300点）

  • 問題文の条件は、どれか一つを削除した場合と同値
  • 全通りを試して、最大値が答え
  • 普通にやるとTLEするので、累積和ならぬ累積gcdして計算量を落とす

参考


import fractions


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

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

参考（愚直な列挙＝TLE）

import fractions
from functools import reduce
import itertools


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

ans = []
for a in list(itertools.combinations(A, N-1)):
    ans.append(reduce(fractions.gcd, a))
print(max(ans))

D - Flipping Signs（400点）

  • 操作を繰り返すと、初期のマイナスの数が偶数の場合は最終的にマイナスを0個に、奇数の場合は1個にできる
  • 奇数の場合にマイナスを付けるのは絶対値が最も小さい値

マイナスの数が1個以下になる理由については、下記で図を用いて説明されています。

drken1215.hatenablog.com

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

num_of_minus = sum([a < 0 for a in A])
abs_A = [abs(a) for a in A]
ans = sum(abs_A)

if num_of_minus % 2 == 0:
    print(ans)
else:
    print(ans - 2 * min(abs_A))