Google Code Jam Qualification 2010 C

メモ化に手間取った。

コードが長いなあ。

3問解くのに3時間もかかってしまった。1,2時間で解けるはずとGoogleは言っているのに。

public void run(String file) throws Exception {

Scanner scan = new Scanner(file);

int T = scan.nextInt();

for (int testcase = 0; testcase <>

int R = scan.nextInt();

int k = scan.nextInt();

int N = scan.nextInt();

int[] gs = new int[N];

for (int i = 0; i <>

gs[i] = scan.nextInt();

}

long[] memmoney = new long[N];

int[] memfreq = new int[N];

Arrays.fill(memmoney, -1L);

Arrays.fill(memfreq, -1);

int cur = 0;

int freq = 0;

long summoney = 0;

int i = 0;

for (i = 0; i <>

if (memfreq[cur] == -1) {

memmoney[cur] = summoney;

memfreq[cur] = freq;

} else {

break;

}

int cap = k;

int stop = 0;

while (cap >= gs[cur] && stop <>

cap -= gs[cur];

cur = (cur+1) % N;

stop++;

}

freq++;

summoney += k - cap;

}

long ans = 0;

if (i == R) {

ans = summoney;

} else {

int f = freq - memfreq[cur];

long fmoney = summoney - memmoney[cur];

int repeated = (int)((R - memfreq[cur]) / f);

int remain = R - memfreq[cur] - (int)((R - memfreq[cur]) / f) * f;

ans = memmoney[cur] + fmoney * repeated;

long plus = -1L;

for (int j = 0; j <>

if (memfreq[j] == memfreq[cur] + remain) {

plus = memmoney[j] - memmoney[cur];

}

}

assert(plus >= 0L);

ans += plus;

}

write("Case #" + (testcase+1) + ": " + ans + "\n");

}

}