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");

}

}

Google Code Jam Qualification 2010 B

紙で計算してみると、t1-t2, t2-t3, t(n-1) - t(n)のgcdをTとして、
t1+yがTの倍数となる最小のyを計算すればよさそうだが、数学的に証明ができない。
まあ、正解だったから、解説が出るまで待ってみよう。

public void run(String file) throws Exception {
Scanner scan = new Scanner(file);
int T = scan.nextInt();
for (int testcase = 0; testcase < T; testcase++) {
int N = scan.nextInt();
BigInteger[] ts = new BigInteger[N];
for (int i = 0; i < N; i++) {
ts[i] = new BigInteger(scan.next());
}
BigInteger[] ds = new BigInteger[N-1];
for (int i = 0; i < N-1;i++) {
ds[i] = ts[i+1].subtract(ts[i]).abs();
}
BigInteger gcd = ds[0];
for (int i =1; i < ds.length;i++) {
gcd = gcd.gcd(ds[i]);
}
//debug(ts, ts[0], gcd);
BigInteger ans = gcd.subtract(ts[0].mod(gcd)).mod(gcd);
write("Case #%d: %s\n", testcase+1, ans.toString());
}
}

Google Code Jam Qualification 2010 A

Aはまずは簡単でした。

ビット演算を使えば綺麗だったか。

public void run(String file) throws Exception {

Scanner scan = new Scanner(file);

int T = scan.nextInt();

for (int testcase = 0; testcase <>

int N = scan.nextInt();

int K = scan.nextInt();

boolean ok = true;

for (int i = 0; i <>

if (K % 2 == 1) {

K = K / 2;

} else {

ok = false;

break;

}

}

if (ok) {

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

} else {

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

}

}

}