mitosoupのブログ

何かあれば、お気軽にご連絡ください。twitter:@mitsoup

AtCoder Beginner Contest 019 C

問題

https://beta.atcoder.jp/contests/abc019/tasks/abc019_3

2の倍数の種類を数え上げる。

単純に行う、つまり例えば、リストをソートして小さいものから順に二倍して探索するなどした場合、TLEしてしまう。

 

やった方法

2で割り続けて発生する、異なる奇数を全て数え上げれば良い。おおよそlog(max(a))で終わる見込みが持てる。

 

コード

Pythonです。C++は修行中

n = int(input())
a = list(set(map(int,input().split())))
al = []
while True > 0:
    for i in range(len(a)):
        if a[i] % 2 == 1:
            al.append(a[i])
            a[i] = 0
        elif a[i] != 0 :
            a[i] = a[i] // 2
        else:
            None
    b = list(set(a))
    if 0 in b:
        b.remove(0)
    if b == []:
        break
    else:
        a = b

print(len(list(set(al))))

改善点があれば教えて頂けると幸いです。