AtCoder Beginner Contest 061 - C / 064 - C

beta.atcoder.jp

基数ソートで計算量N。 普通のソートはNlogNなのでソートそのものは間に合うけれども 挿入回数が10¹⁰まで行くのでばらばらに数値を扱うと間に合わなさそう。

def solve(N, K, ABs):
    counts = {i: 0 for i in range(1, 10 ** 5 + 1)}
    for a, b in ABs:
        counts[a] += b
    s = 0
    for c, count in counts.items():
        s += count
        if K <= s:
            return c


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = []
    for _ in range(N):
        ABs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, ABs))

この辺りはアルゴリズムイントロダクション様様。 セールで半額で買ったけど良い買い物したと思う。

books.rakuten.co.jp

beta.atcoder.jp 商の種類のカウント。 質問を見逃して、8種類以上にはならないと思っててはまった。 あと色は選ばなくてはならない、のでALLが一人だけいたら最低1つの色は使うことになる。

def solve(N, As):
    colors = set()
    allcount = 0
    for a in As:
        n = a // 400
        if n < 8:
            colors.add(n)
        else:
            allcount += 1
    return max(len(colors), 1), len(colors) + allcount


if __name__ == "__main__":
    N = int(input())
    As = map(int, input().split(" "))
    m1, m2 = solve(N, As)
    print(m1, m2)