GCJ 2010 Qualification Round C.Theme Park

program

問題

http://code.google.com/codejam/contest/dashboard?c=433101#s=p2

  • それぞれ、g_0, ..., g_{n - 1} 人から成る n 個のグループが遊園地のジェットコースターに乗る。
  • ジェットコースターには k 人同時に乗れる。
  • ジェットコースターは1日に r 回走る。
  • ジェットコースターには、列の先頭に居るグループから、順番に、k 人を超えない範囲で出来るだけたくさんが搭乗する。
    • この時、列の n 番目のグループが乗れないなら、n + 1 番目以降も、その回には乗らない。
  • ジェットコースターに乗ったグループは、列の最後に並ぶ。
  • この遊園地の営業時間は超長い or ジェットコースターが超スピーディー。1日で、最大 ジェットコースターは 10^8 回くらい走る。
  • さらに、このジェットコースターも超長い。最大で、10^9 人乗れる。

方針

  • 単純には、遊園地の営業開始から、シミュレーションすれば良いけど、時間が足りない。
  • グループ数の最大値は小さいので、各グループ i に対して、列の先頭が グループ i だった時、その回に何人が乗れるか、次の回の先頭グループはどこか, を予め計算しておく。

答案

/*! if g++ -Wall -g ThemePark.cpp; then ./a.out < test.in; fi
 */

#include <iostream>
#include <vector>
#include <string>
#include <iterator>

using namespace std;
typedef unsigned long long ull;

void makeMemo(vector<ull>& nextTop, vector<ull>& revenue, vector<ull>& g, ull n, ull k){
  nextTop.resize(n);
  revenue.resize(n);
  for(ull i = 0; i < n; i++){
    ull j;
    revenue[i] = 0;
    for(j = 0; j < n; j++){
      if(revenue[i] + g[(i + j) % n] > k) break;
      revenue[i] += g[(i + j) % n];
    }
    nextTop[i] = (i + j) % n;
  }
}

void solve(ull r, ull k, ull n, vector<ull>& g, int caseNum){
  vector<ull> nextTop, revenue;
  makeMemo(nextTop, revenue, g, n, k);

  ull ret = 0;
  ull next = 0;
  for(ull i = 0; i < r; i++){
    ret += revenue[next];
    next = nextTop[next];
  }

  cout << "Case #" << (caseNum + 1) << ": " << ret << endl;
}

int main(int argc, char* argv[]){
  int t;
  cin >> t;

  for(int i = 0; i < t; i++){
    ull r, k, n;
    cin >> r >> k >> n;

    vector<ull> g(n);
    for(ull j = 0; j < n; j++){
      cin >> g[j];
    }

    solve(r, k, n, g, i);
  }

  return 0;
}