/2 and *3 [第八回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202109-open/tasks/past202109_i

解説

https://atcoder.jp/contests/past202109-open/submissions/26690153

難しい問題。色々方針が思い浮かぶかもしれないが、思いつかないと中々厄介だろうと思う。

本質を見抜く

実は、今回の操作はやればやるだけ状況が改善される。
操作で÷2を行ったときに最小値がより小さくなってしまった場合は自分に×3をすればいい。
なので、すべての数をチェックして最大何回操作を行えるかを確認して、その最大回数操作を行うことにしよう。

加えてもう1つ便利な性質として全体でcnt回操作が行えるときに、全体で÷2をcnt回、×3をcnt回行うことができるが、
÷2の操作が×3の操作に影響はせず、逆もまたしかりなので、最初に÷2をcnt回してしまって、最後に×3をcnt回行っても
問題ない。

おさらいすると、以下の性質が問題を解くうえで便利である。

• すべての数をチェックして最大何回操作を行えるかを確認して、その最大回数操作を行う
• 最初に÷2をcnt回してしまって、最後に×3をcnt回行っても問題ない

最適動作を考える

÷2はどのように操作をしても結果は変わらないので、操作後は一意な状態となる。
ここから適切に×3をcnt回行うことで最小値を最大化したい。
これには貪欲に小さい数から優先的に×3を行っていくことで実現できる。
なので、N個の数から最小値を高速に取り出して×3をして入れなおすということを繰り返すことができればACできる。
このために優先度付きキューを使うことができる。
C++では要素の最大値を返すようになっているので負数を使うか比較関数を用意することで最小値を返すように改造すること。

操作回数の最大値

特に工夫しなくても操作をそのまま実装すれば今回は間に合う。
計算量のキーになりそうなのが、操作回数の最大値であるが、これは÷2を行う最大回数と一致する。
÷2をしていくと急激に数が小さくなっていく、もう少し正確に書くと、最大回数はlog2(10⁹)くらいになるので、30回とかそんなもん。
なので30N回くらいが最大値でこれは全部普通に行っても計算時間的には間に合う。

int N; ll A[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    min_priority_queue<ll> que;
    int cnt = 0;
    rep(i, 0, N) {
        while (A[i] % 2 == 0) cnt++, A[i] /= 2;
        que.push(A[i]);
    }
    rep(i, 0, cnt) {
        ll top = que.top() * 3;
        que.pop();
        que.push(top);
    }

    ll ans = que.top();
    cout << ans << endl;
}