AtCoder Beginner Contest 019 C
問題
https://beta.atcoder.jp/contests/abc019/tasks/abc019_3
2の倍数の種類を数え上げる。
単純に行う、つまり例えば、リストをソートして小さいものから順に二倍して探索するなどした場合、TLEしてしまう。
やった方法
2で割り続けて発生する、異なる奇数を全て数え上げれば良い。おおよそlog(max(a))で終わる見込みが持てる。
コード
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))))
改善点があれば教えて頂けると幸いです。