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_iA倍していって最大値を超えるまで操作をするということなので、高々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^na_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;
    }
}