(倍々は計算量軽い)ARC-051-C-掛け算

問題URL→http://arc051.contest.atcoder.jp/tasks/arc051_c

ある時点の数列を昇順に並べた時に、a_1 * A >= a_Nとなると以降はa_1,a_2,a_3,・・・a_Nの順で周期的に更新されていくことになる。
よって周期的になるまでは愚直にシミュレーションして、周期に入ったら、その周期で割り算すればいい。

最初の愚直なシミュレーションだが、A=1の場合はコーナーケースでこれを除外すると、
計算量はO(N * log(max(a_i)))くらいになる。

倍々の計算量は軽いと覚えておこう。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod = MOD)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int N, A, B;
int a[55];

signed main()
{
    cin >> N >> A >> B;
    REP(i,N) cin >> a[i];

    sort(a, a + N);
    if (A == 1) {
        REP(i,N) cout << a[i] << endl;
        return 0;
    }

    while (B > 0) {
        if (a[N-1] <= A * a[0]) {
            break;
        }
        a[0] *= A;
        sort(a, a + N);
        B--;
    }

    if (B == 0) {
        REP(i,N) cout << a[i] % MOD << endl;
        return 0;
    }

    int mul = B / N;
    int remain = B % N;
    for (int i=remain; i<N; i++) {
        cout << a[i] * mod_pow(A, mul) % MOD << endl;
    }
    REP(i,remain) {
        cout << a[i] * mod_pow(A, mul + 1) % MOD << endl;
    }
}

(難しいシミュレーション)ARC-082-F-Sandglass

問題URL→http://arc082.contest.atcoder.jp/tasks/arc082_d

時刻tの始めのAの砂量aのときの砂量をf_t(a)という関数であらわす。
するとこの関数のグラフは多くても2回曲がる直線のグラフになるので、
解説や解説動画のとおり始めに曲がるx座標、次に曲がるx座標、y切片をもってシミュレーションできる。

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) for(ll i=1;i<=(n);i++)
#define MOD 1000000007
#define int long long
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9;

ll T;   //合計T[g]の砂
int K;  //砂時計をひっくり返す回数
int Q;  //クエリ数

signed main()
{
    cin >> T;
    cin >> K;
    set<P> events;
    REP(i,K) {
        int t;  //ひっくり返す時刻。元から昇順で並んでいる
        cin >> t;
        events.insert(P(t, -1));    //reverse query
    }
    cin >> Q;
    REP(i,Q) {
        ll t;   //時刻
        ll f;   //始めのAの砂の量
        cin >> t >> f;
        events.insert(P(t, f));
    }

    bool inc = false;   //A,Bどちらが上か。Aが上のときfalse
    ll pt = 0;  //カーソル
    ll a = 0;
    ll b = T;
    ll c = 0;
    for (P e : events) {
        ll t = e.first;     //ひっくり返す、もしくはクエリの時刻
        ll x = e.second;    //-1ならreverse query。そうでないならAの始めの砂の量

        if (inc) {  //Bが上
            ll d = t - pt;  //カーソルから進んだ時間
            c += d;
            if (b + c > T) b = T - c;
            if (a > b) a = b;
        } else {    //Aが上
            ll d = t - pt;  //カーソルから進んだ時刻
            c -= d;
            if (a + c < 0) a = -c;
            if (a > b) b = a;
        }
        if (x == -1) {  //reverse
            inc = !inc;
        } else {
            cout << max(a, min(b, x)) + c << endl;
        }
        pt = t;
    }
}