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のブートプロセスなどと並行してゴリゴリやるか。