Find the Min

問題

数列の内、頭の k 項が知らされている。残りについては、"直前 k 項に現れない、最小の非負整数"という条件もわかっている。この時数列の最後 n 項目は何か。

考え方

• 初項 k 項については乱数だけど 10^9 まである掛け算だから 64bit 使おう
• 未知部分については、とりあえず k+1 より大きい数が現れるはずはない
• むしろ k+1 周期でループするんじゃん。
• まずは m[0..k] を計算しておこう。
• [k] だけは疑似乱数の枠じゃないから別計算だな。
• m[k+1..2k+1] を求められれば m[(n-1)%(k+1)] が答えじゃん。
• 使える／使えない数のリストを持たないとなー。
• 使える数は最小が云々だからsetで、使えないのは配列/vectorでいいか。

コード

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long int64;

void PseudoRand(const int n, vector<int>* data) {
  int64 a, b, c, r;
  cin >> a >> b >> c >> r;
  for (int64 i = 0; i < n; ++i) {
    (*data)[i] = static_cast<int>(a);
    a = (b * a + c) % r;
  }
}

int64 Solve() {
  int n, k;
  cin >> n >> k;

  // Input and generate
  vector<int> data(k + 1);
  PseudoRand(k, &data);

  // Set up
  vector<int> used(k + 1, 0);
  for (int i = 0; i < k; ++i) {
    const int d = data[i];
    if (d <= k + 1)
      ++used[d];
  }
  set<int> usable;
  for (int i = 0; i <= k; ++i) {
    if (used[i] == 0)
      usable.insert(i);
  }

  // Set m[k]
  {
    set<int>::iterator itr = usable.begin();
    data[k] = *itr;
    ++used[*itr];
    usable.erase(itr);
  }

  // Make m[(k+1) .. 2*(k+1)-1]
  for (int i = 0; i <= k; ++i) {
    const int d = data[i];
    if (d <= k + 1 && used[d] > 0) {
      --used[d];
      if (used[d] == 0)
	usable.insert(d);
    }

    set<int>::iterator itr = usable.begin();
    data[i] = *itr;
    usable.erase(itr);
  }

  return data[(n - 1) % (k + 1)];
}


int main(void) {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": " << Solve() << "\n";
  }
}