AtCoder Beginner Contest 061 - C / 064 - C

beta.atcoder.jp

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

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)

AtCoder Beginner Contest 054 - C / 057 - C

beta.atcoder.jp

無向グラフの探索。再帰よりもキューのほうが好き。深さ優先と幅優先の切り替えが楽だから。

def solve(N, M, Es):
    al = {}
    for e in Es:
        al.setdefault(e[0], []).append(e[1])
        al.setdefault(e[1], []).append(e[0])

    ans = 0
    q = [(1, [1])]
    while len(q) > 0:
        current, history = q.pop()
        nexts = al[current] if current in al else []
        if len(history) == N:
            ans += 1
        for n in nexts:
            if n not in history:
                nhist = history[:]
                nhist.append(n)
                q.append((n, nhist))
    return ans


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

beta.atcoder.jp

簡単な因数分解。300点でも波があるな。

因数を探すとき、上限が√Nであるのはよいのだけれど、下を少し気にしなくてはいけない。 素因数分解だとrangeの最初は2。Nを割りながら探すために1にすると無限ループになってしまう。 逆に単なる因数はNが素数の時を考慮しなくてはならないので、1になる。

def solve(N):
    ret = []
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ret.append(max(len(str(i)),
                           len(str(N // i))))
    return min(ret)


if __name__ == "__main__":
    N = int(input())
    print(solve(N))

pythonはmin / max / all / anyあたりを覚えたらかなり行数が減った気がする。

AtCoder Beginner Contest 042 - C / 044 - C

Tenka1のログインアカウント間違えて参加してしまった。。 とはいえ、300点、400点問題あたりに壁を感じるので過去問練習。

abc042.contest.atcoder.jp

数が少ないので総当たり。最大 2N 回繰り返されるかな。

def solve(N, K, Ds):
    while True:
        c = set([int(c) for c in str(N)])
        if len(c.intersection(Ds)) == 0:
            return N
        N += 1

abc044.contest.atcoder.jp

再帰で頑張ろうとしたがうまくいかなかったので、総当たりに変更。 頻出だけれどN個の0と1の組み合わせは0~2のN乗の2進数表示でどうにかなる。format記法が覚えられない。 計算量が少なければ、初めから総当たりにすべきだった。 別解への挑戦は一度終わってからにしよう。本番のように練習を。

def solve(S):
    l = 2 ** (len(S) - 1)
    sum = 0
    for i in range(l):
        bi = ("{:0%db}" % (len(S) - 1)).format(i)
        ope = []
        for b in bi:
            if b == "0":
                ope.append("")
            else:
                ope.append("+")
        ope.append("")
        p = ""
        for s, o in zip(S, ope):
            p += s
            p += o
        sum += eval(p)
    return sum

アルゴリズムの勉強はしてきたが、実装力が追い付いてないのでまたそろそろ OS自作入門、Linuxのブートプロセスなどと並行してゴリゴリやるか。