ABC169

Atcoder Beginner Contest 169#atcoder Bはオーバーフローしてからでも0がきたら0になるのに気づいてなかったが、サンプルケースで落としてくれるので親切。

Cはハマって時間を消費した人もいるようだけど僕は初手「小数点を文字列置換して整数演算」であっさり通りました。なお int(0.29 * 100) == 28 です。 python

A, B = input().split()
A = int(A)
B = int(B.replace(".", ""))
print(A * B // 100)

Dは素因数分解して三角数と比較。素因数分解がタイムアウトにならないか肌感がないので不安で「素数テーブル埋め込むか？」と思ったりもした。 「早すぎる最適化は諸悪の根源」なので、いったん素朴な方法でやって、タイムアウトしてから高速化するつもりで投げたら一発で通った。 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:
        factors[p] += 1
        N //= p
if N != 1:
    factors[N] = 1

# print(factors)
result = 0
for p in factors:
    fp = factors[p]
    ti = 1
    while True:
        # print(p, fp, ti)
        if fp >= ti:
            fp -= ti
            ti += 1
            result += 1
        else:
            break

print(result)

Eは「中央値になりうる値」の上限と下限を求めて間の数を数える植木算でした 「中央値になりうる値の下限」は「値の範囲の下限の中央値付近」なので、上限と下限をそれぞれソートして真ん中あたりを読む方針 境界条件が怪しいので、大筋書き終わったタイミングでいったん投げてタイムアウトにならないことを確認して(タイムアウトになるようならアルゴリズムを根本的に見直す必要があるから細かいテストをしても意味がない)それからテストケースを書き始めた python

TEST = False

if not TEST:
    N = int(input())
    AS = []
    BS = []
    for i in range(N):
        A, B = [int(x) for x in input().split()]
        AS.append(A)
        BS.append(B)


def getBound(AS, BS):
    """
    >>> getBound([0, 1], [1, 2])
    1 3 3
    >>> getBound([0, 0], [1, 2])
    1 3 3
    >>> getBound([0, 1, 2], [1, 2, 3])
    1 2 2
    >>> getBound([0, 1, 2], [1, 3, 3])
    1 3 3
    >>> getBound([0, 0, 1], [2, 3, 3])
    0 3 4
    """
    N = len(AS)
    AS2 = AS[:]
    AS2.sort()

    BS2 = BS[:]
    BS2.sort()
    if N % 2 == 0:
        lower = AS2[N // 2 - 1] + AS2[N // 2]
        upper = BS2[N // 2 - 1] + BS2[N // 2]
        result = upper - lower + 1
    else:
        lower = AS2[N // 2]
        upper = BS2[N // 2]
        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://note.nkmk.me/atcoder-python-numpy-scipy-version/ 標準ライブラリ以外も使えるのか、知らなかった