ABC169
https://gyazo.com/b5e51a38e875de48224f6fe4ee0a7669
Bはオーバーフローしてからでも0がきたら0になるのに気づいてなかったが、サンプルケースで落としてくれるので親切。
Cはハマって時間を消費した人もいるようだけど僕は初手「小数点を文字列置換して整数演算」であっさり通りました。なお int(0.29 * 100) == 28 です。
code:python
A, B = input().split()
A = int(A)
B = int(B.replace(".", ""))
print(A * B // 100)
Dは素因数分解して三角数と比較。素因数分解がタイムアウトにならないか肌感がないので不安で「素数テーブル埋め込むか？」と思ったりもした。
「早すぎる最適化は諸悪の根源」なので、いったん素朴な方法でやって、タイムアウトしてから高速化するつもりで投げたら一発で通った。 code:python
from math import sqrt
from collections import defaultdict
N = int(input())
factors = defaultdict(int)
upper = int(sqrt(N))
for p in range(2, upper + 1):
while N % p == 0:
N //= p
if N != 1:
# print(factors)
result = 0
for p in factors:
ti = 1
while True:
# print(p, fp, ti)
if fp >= ti:
fp -= ti
ti += 1
result += 1
else:
break
print(result)
Eは「中央値になりうる値」の上限と下限を求めて間の数を数える植木算でした
「中央値になりうる値の下限」は「値の範囲の下限の中央値付近」なので、上限と下限をそれぞれソートして真ん中あたりを読む方針
境界条件が怪しいので、大筋書き終わったタイミングでいったん投げてタイムアウトにならないことを確認して(タイムアウトになるようならアルゴリズムを根本的に見直す必要があるから細かいテストをしても意味がない)それからテストケースを書き始めた
code:python
TEST = False
if not TEST:
N = int(input())
AS = []
BS = []
for i in range(N):
AS.append(A)
BS.append(B)
def getBound(AS, BS):
"""
1 3 3
1 3 3
1 2 2
1 3 3
0 3 4
"""
N = len(AS)
AS2.sort()
BS2.sort()
if N % 2 == 0:
result = upper - lower + 1
else:
result = upper - lower + 1
if TEST:
print(lower, upper, result)
else:
return result
def _test():
import doctest
doctest.testmod()
if TEST:
_test()
else:
print(getBound(AS, BS))
https://gyazo.com/0abed2cc8ce19a58ebfbabf7209f976b
パフォーマンスというのはずっと維持してればレーティングがそれに収束するような値らしい
標準ライブラリ以外も使えるのか、知らなかった