AtCoder ABC 100 C - *3 or /2 (灰色, 300 点)

結構好きな問題

• ABC 100 C - *3 or /2

問題概要

N 個の整数 a1, a2, ..., aN があって 1 回の操作で以下が行える

• 各整数について「3 倍」「2 で割るなら 2 で割る」のいずれかを行う
• どれかの整数については「2 で割る」の方をしなければならない

最大で何回操作を行えるか？

制約

• 1 <= N <= 10⁴

解法

「a を 2 で何回割れるか」は、a を 3 倍しても変わらない。
よって、操作は

• 少なくとも 1 個以上の整数について 2 で割る

としてよい。さらに操作回数を最大化したいので、1 個だけ 2 で割るとしてよい。したがって、各 ai についての「2 で何回割れるか」を合計する。

コード

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<long long> a;

int main() {
    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        int tmp = 0;
        while (a[i] % 2 == 0) {
            ++tmp;
            a[i] /= 2;
        }
        res += tmp;
    }
    cout << res << endl;
}