B - 価格の合計 | AtCoder Beginner Contest 014

B - 価格の合計 | AtCoder Beginner Contest 014

解法

問題文の誘導どおりにXの2進表記のi番目のbitが立っているかどうかを判定し和を取る．

コーナーケース検討

価格の総和は $\sum_{i=0}^{n-1} a_{i} < 1000 * 2^{20} < 2^{31}$ 程度なのでintに収まる．

実装

Xの2進表記のi番目のbitが立っているかどうかをX & (1 « i)で判定出来る．

int a[20] = {};
int sum = 0;
REP(i, n){
    cin >> a[i];
}
REP(i, n){
    if (X & (1 << i)) sum += a[i]; 
}
cout << sum << endl;

Submission

データ構造・アルゴリズム

• bit演算