はまやんはまやんはまやん

hamayanhamayan's blog

Ice Rink Game [AtCoder Grand Contest 020 B]

https://beta.atcoder.jp/contests/agc020/tasks/agc020_b

解法

https://beta.atcoder.jp/contests/agc020/submissions/1974220

最小の値と最大の値について考えてみると、その間の数も全て条件をみたしそうな感じがある。
こういう有効な範囲を答える問題は範囲を更新しながら解を求めていきそうな雰囲気がある。
なので、この方針で考えてみると操作を逆にやってみることで求めていく。

最小の値をL, 最大の値をRとして更新していく。
最初は2人だけ残るのでL=R=2
後ろからA[i]を使って更新していく。
更新は「x' = floor(x / A[i]) * A[i]」として更新する。
そのため、「L' = ceil(L / A[i]) * A[i]」として更新する。
この時に、R

int K;
ll A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K;
    rep(i, 0, K) cin >> A[i];
 
    ll L = 2, R = 2;
    rrep(i, K - 1, 0) {
        L = (L + A[i] - 1) / A[i] * A[i];
        if (R < L) {
            printf("-1\n");
            return;
        }
 
        R = (R / A[i] + 1) * A[i] - 1;
    }
 
    printf("%lld %lld\n", L, R);
}