ABC014「B - 価格の合計」をPythonで解く

ABC014「B - 価格の合計」をPythonで解いた。

解法

AtCoder Beginner Contest 014 解説 from AtCoder Inc.

解答

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

ans = 0

for i in range(N):
    if (X>>i)&1 == 1:
        ans += a[i]

print(ans)

解説

問題文に書いてある通り、Xのk番目のビットが立っている価格を足し上げる
「Xのk番目のビットが立っている」という条件をどう書くかという問題

途中経過を含めて出力してみる。

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

ans = 0

print("===bin(X)===")
print(bin(X))
print("===bin(1)===")
print(bin(1))
print("===bin(X>>0)===")
print(bin(X>>0))
print("===bin(X>>1)===")
print(bin(X>>1))
print("===bin(X>>2)===")
print(bin(X>>2))
print("===bin(X>>3)===")
print(bin(X>>3))
print("===bin((X>>0)&1)===")
print(bin((X>>0)&1))

for i in range(N):
    if (X>>i)&1 == 1:
        ans += a[i]

print("===ans===")
print(ans)

❯ python B.py
4 5
1 10 100 1000
===bin(X)===
0b101
===bin(1)===
0b1
===bin(X>>0)===
0b101
===bin(X>>1)===
0b10
===bin(X>>2)===
0b1
===bin(X>>3)===
0b0
===bin((X>>0)&1)===
0b1
===ans===
101

(X>>i)でXの桁がi個ズレていき、((X>>0)&1)の演算で、以下が返る。