けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

今週のお題「2018年上半期」

好きなのん

ABC 100 C - *3 or /2

問題概要

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

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

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

制約

  • 1 <= N <= 104

解法

「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;
}