AtCoder Regular Contest 051 C - 掛け算

問題

　 $N(\le 50)$ 個の整数 $a_1, \dots, a_N(\le 10^9)$ が与えられる。「一番小さいものを $A(\le10^9)$ 倍する」という操作を $B(\le 10^9)$ 回繰り返した後の整数たちを昇順に並べ出力せよ。

解法

　解説PDFの通り。

　 $a_1, \dots, a_N$ がソートしてあるとして、 $a_1 \times A \ge a_N$ ならばそのあと操作される整数は $a_1, a_2, \dots, a_N, a_1, a_2, \dots, a_N, a_1, a_2, \dots$ となる。したがってそれ以降 $A$ が何回かけられるかは簡単に求めることができる。

　 $a_1 \times A \ge a_N$ になるまでは愚直にシミュレーションするとすると、これは最大値以外の $a_i$ を $A$ 倍していって最大値を超えるまで操作をするということなので、高々 $O(N\log{(\max{a_i})})$ 程度の計算量である。最小値の探索に $O(N)$ かかったとしても $O(N^2\log{(\max{a_i})})$ 。

　シミュレーションが終わったあとは高速な累乗を用いて $O(N\log{B})$ (ここは解説PDFでは $O(N\log{A})$ とあったが違う気がする。自分の勘違いだろうか)で計算できるので、これでこの問題が解けた。

反省

　1時間20分(2WA)でAC。

　最初のころは $\log_A{a_i}$ を考えていけば解けるのかと思ったが、最終的に高速累乗を使わなければならないことは目に見えていて、それだと整数型でかける回数を持っていないとダメだということに気づいて頓挫。

　よってこれを商と余り、みたいな感じで $A^n$ が $a_i$ を超えない最大の $n$ と、そのときの残り部分を持って、 $a_i = A^n + p$ というように分解すれば解けそうと思って実装していく。全操作後の最小な $n$ について二分探索をして、必要な最小操作回数が $B$ となるように求めていく方針でいけると思っていた。

　1時間経ったくらいタイミングでサンプル1と2は合うものができたが、サンプル3がどうしても合わなず、しばらく格闘したが諦めて解説を見た。

　各 $i$ について $n$ の最大と最小が高々1しか差がないことはサンプルの3のデバッグをしているときに気づいたのに、それでシミュレーションすればいいという発想に至らなかった。これはなかなか気づきが必要で難しいように思えるが、問題の考察が足りなかったということだろう。すぐ知っているアルゴリズムに結び付けようとしてしまうが、その前にもっと問題自体の性質を考えなくてはならないなぁ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

ll MODpow(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m % 2 == 1) {
            result *= n;
            result %= MOD;
        }

        m /= 2;
        n *= n;
        n %= MOD;
    }

    return result;
}

int main() {
    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    if (A == 1) {
        for (ll e : a) {
            cout << e % MOD << endl;
        }
        return 0;
    }

    while (true) {
        auto min_itr = min_element(a.begin(), a.end());
        if (*min_itr * A >= *max_element(a.begin(), a.end())) {
            break;
        }
        *min_itr *= A;
        if (--B == 0) {
            sort(a.begin(), a.end());
            for (ll e : a) {
                cout << e % MOD << endl;
            }
            return 0;
        }
    }

    sort(a.begin(), a.end());
    for (ll i = B % N; i < N; i++) {
        cout << a[i] * MODpow(A, B / N) % MOD << endl;
    }
    for (ll i = 0; i < B % N; i++) {
        cout << a[i] * MODpow(A, B / N + 1) % MOD << endl;
    }
}