Facebook hacker cup Qualification Round

問題3

非負整数列 aは以下の性質を満たす数列である。 「aの要素は、直前のk個の要素に含まれない最小の数である。」 最初のk項が与えられるので、n番目の要素の値を求めよ。

制約

解法

考察してみると, a[k]からa[k + k + 1]までの列が繰り返されていることがわかる。 その数列は、priority_queueを使えばO(klogk)で計算できる。

コード

int main(){
  int T; cin>>T;
  REP(CASEN, T){
    printf("Case #%d: ", CASEN + 1);
    int N, K;
    cin>>N>>K;
    ll A, B, C, R;
    cin>>A>>B>>C>>R;

    vector<int> use_cnt(2 * K, 0);
    queue<ll> M;
    for(int i = 0; i < K; i++){
      if(A < 2 * K) use_cnt[A] += 1;
      M.push(A);
      A = (B * A + C) % R;
    }

    priority_queue<int, vector<int>, greater<int> > que;
    REP(i, 2 * K) if(use_cnt[i] == 0) que.push(i);

    if(N - K <= K + 1){
      REP(iter, N - K - 1){
        que.pop();
        int f = M.front(); M.pop();
        if(f < 2 * K && --use_cnt[f] == 0) que.push(f);
      }
      int ans = que.top();
      cout<<ans<<endl;
    }else{
      vector<int> a(K + 1);
      REP(i, K + 1){
        a[i] = que.top(); que.pop();
        int f = M.front(); M.pop();
        if(f < 2 * K && --use_cnt[f] == 0) que.push(f);
      }
      int idx = (N - K - (K + 1) + (K + 1 - 1)) % (K + 1);
      cout<<a[idx]<<endl;
    }
  }
  return 0;
}