ゲーム(AGC020B - Ice Rink Game)

問題

atcoder.jp

単純に逆から辿っていくので結構計算量も小さそうなんだけど、正確なところはわからないので、とりあえず実装してみよう。->計算量K(10^5)で操作できた。

すごく時間がかかってしまった（最初から思いついてたんだけど例外がないか確かめるのに時間がかかった）。本番ではとりあえずだいたいよさそうなものを見つけたらすぐにきっちり定式化して実装してしまったほうがよさそう。

解法

を最初の人数、を1回目の操作(-する操作とする)が終わった後の人数…とする。

この時、とは必ず2である。こういう感じに逆算して行くだけ。

具体的には、としてありえる数字として最大のものRと最小のものLがわかっている時、に付いて以下。

としてありえる最小のものは[L,R]のうちで割り切れるもののうち最小のもの

としてありえる最大のものは[L,R]のうちで割り切れるもののうち最小のもの+(A[j]-1)

R

別解

操作を関数とすると広義単調増加なので、その合成関数も広義単調増加。

よって二分探索によって、1以上2+K*max(A_i)以下の中から可能なNを求めることができる。

log( K*max(A_i) )の二分探索で、一ループあたりK回操作するので計算量はK*log( K*max(A_i) )

コード

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back

int K;
int A[100004];

signed main(){
    scanf("%lld",&K);
    rep(i,K){
        scanf("%lld",&A[i]);
    }
    A[K]=1;
    int L=2,R=2;
    rep(i,K){//N_jの値を求めて次に進むループ
        int j=K-1-i;
        L%A[j]?L=((int)(L/A[j])+1)*A[j]:L=L ;
        R=(R-R%A[j])+A[j]-1;
       if(L>R){printf("-1\n");return 0;}
    }
    printf("%lld %lld\n",L,R);
}