[Python] ABC019 C

問題

C – 高橋くんと魔法の箱

回答

スライドに従い、50点回答を求めます。

AtCoder Beginner Contest 019 解説 from AtCoder Inc.

N = int(input())
a = list(map(int, input().split()))

#ある数 x に対する結果と 2x に対する結果が同じなので，
# a[i] が2で割り切れなくなるまで2で割り続ける。
# この処理で，a[i] がすべて奇数になった問題になる。
# 逆に，奇数で異なる数に対する答えをまとめて求めることは不可能。
def divide_by_2_till_odd(x):
    while x % 2 == 0:
        x //= 2
    return x

a_odd = list(map(divide_by_2_till_odd, a))

# 20点解法
# n<=3000 なので，a[i] が a[j] (1<=j<i) のいずれかに等しいかをすべてチェックし。
# いずれにも等しくないとき，ai の種類を1増やす
def solve20(a):
    cnt = 0
    for i in range(len(a)):
        for j in range(i):
            if a[i] == a[j]:
                break
        else:
            cnt += 1
    
    return cnt

#30点解法
# a[i]<=300000 なので，ある数が現れたかどうか，
# という長さ 300000 の配列を取り，それぞれのa[i]について，現れたことをメモする． 
# 最後に現れたことのある数を数える．
def solve30(array):
    memo = [False] * (5 * 10 ** 5 + 1)
    for a in array:
        if memo[a]:
            continue
        memo[a] = True
    return sum(memo)


if N <= 3000:
    print(solve20(a_odd))
else:
    print(solve30(a_odd))

AtCoder Beginner Contest 019 解説 from AtCoder Inc.

集合を使い、100点回答を求めます。

N = int(input())
a = list(map(int, input().split()))

#ある数 x に対する結果と 2x に対する結果が同じなので，
# a[i] が2で割り切れなくなるまで2で割り続ける。
# この処理で，a[i] がすべて奇数になった問題になる。
# 逆に，奇数で異なる数に対する答えをまとめて求めることは不可能。
def divide_by_2_till_odd(x):
    while x % 2 == 0:
        x //= 2
    return x

# 集合を使う
a_odd_set = set(map(divide_by_2_till_odd, a))
print(len(a_odd_set))

ソートを使い、100点回答を求めます。

N = int(input())
a = list(map(int, input().split()))

#ある数 x に対する結果と 2x に対する結果が同じなので，
# a[i] が2で割り切れなくなるまで2で割り続ける。
# この処理で，a[i] がすべて奇数になった問題になる。
# 逆に，奇数で異なる数に対する答えをまとめて求めることは不可能。
def divide_by_2_till_odd(x):
    while x % 2 == 0:
        x //= 2
    return x

# ソートを使う
a_odd_sorted = sorted(list(map(divide_by_2_till_odd, a)))
cnt = 1
for i in range(1, len(a_odd_sorted)):
    if a_odd_sorted[i-1] == a_odd_sorted[i]:
        continue
    cnt += 1

print(cnt)