Atcoder ABC 125 を解いてみた(python3)
-A. Biscuit Generator
問題ページ【A - Biscuit Generator】
問題文
ビスケット生産装置を起動すると、起動してから A 秒後、2A 秒後、3A 秒後、... (A の倍数秒後) にB枚ずつビスケットを生産します。
ビスケット生産装置を起動してから T+0.5秒後までに生産されるビスケットの合計枚数を求めてください。
規約
- 入力は全て整数である。
- 1 ≦ A, B, T ≦ 20
考え
時間内に何回ビスケットを生産出来るか求める。
あとは一回の生産で、生産できるビスケットの枚数を掛けてあげればいい。
解法
私のコンテスト中の解法
# -*- coding: utf-8 -*- a, b, t = map(int, input().split()) # 何回生産出来るか p = (t+0.5)//a ans = p*b print(ans)
実行時間：17 ms メモリ：2940 KB
-B. Resale
問題ページ【B - Resale】
問題文
N 個の宝石があり、i 番目の宝石の価値は Viです。
あなたはこれらの宝石の中からいくつかを選んで手に入れます。
このとき、1つも選ばなくとも、全て選んでも構いません。
ただし、i番目の宝石を手に入れる場合コスト Ciを支払わなければいけません。
手に入れた宝石の価値の合計を X、支払ったコストの合計を Yとします。
X−Yの最大値を求めてください。
規約
- 入力は全て整数である。
- 1≦ N ≦ 20
- 1≦ Ci, Vi ≦ 50
考え
つまり宝石を手に入れて、利益が最大になるときを求めるってこと。
N個の宝石それぞれについて利益を求めて、正になったとき合計に足していけばいい。
解法
私のコンテスト中の解法
# -*- coding: utf-8 -*- n = int(input()) v = list(map(int, input().split())) c = list(map(int, input().split())) sum = 0 for i in range(n): xy = v[i]-c[i] if xy >0: sum = sum+xy print(sum)
実行時間：18 ms メモリ：3060 KB
-C. GCD on Blackboard
問題ページ【C - GCD on Blackboard】
問題文
N 個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109
以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。
書き換えた後の N個の整数の最大公約数の最大値を求めてください。
規約
- 入力は全て整数である。
- 2 ≦ N ≦
- 1 ≦ Ai ≦
考え
与えられた数列から一つ数字を飛ばして最大公約数を求める。
その一つ飛ばす位置を変えながら、最大になる最大公約数を探したい。
実装したらTLEになってしまったので、けんちょんさんの精進ブログを参考にさせていただきました。
http://drken1215.hatenablog.com/entry/2019/04/27/224100_1drken1215.hatenablog.com
解法
pythonで実装してみました。
# -*- coding: utf-8 -*- # 最大公約数を求める def gcd(a,b): if b==0:return a return gcd(b,a%b) # 入力 n = int(input()) a = list(map(int, input().split())) # 累積GCD left = [0]*(n+1) right = [0]*(n+1) for i in range(n): left[i+1] = gcd(left[i], a[i]) for i in reversed(range(n)): right[i] = gcd(right[i+1], a[i]) # 集計 ans = 0 for i in range(n): l = left[i] r = right[i+1] print(l,r) ans = max(ans, gcd(l, r)) print(ans)
実行時間：234 ms メモリ：14584 KB
