Google Code Jam Qualification Round 2010

GCJ

Google Code Jam Qualification Round 2010に参加した。3問とも通ったらしい。

A. Snapper Chain

結局、T-FFをN個連結して、クロックをK回入れたらどうなりますかっていう話なので、英語さえ読めればコードは楽勝。

#include <cstdio>
using namespace std;

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 0; t < T; ++t) {
    printf("Case #%d: ", t+1);
    int N, K;
    scanf("%d%d", &N, &K);
    if (K % (1 << N) == (1 << N) - 1)
      puts("ON");
    else
      puts("OFF");
  }
}

B. Fair Warning

一番悩んだ。

条件式を変形していくと

ti + y = 0 (mod T)

ti = -y (mod T)

t1 = t2 = ... = tn = -y (mod T)

t1 = t2 かつ t2 = t3 かつ ... かつ tn-1 = tn (mod T)

t1 - t2 = 0 かつ t2 - t3 = 0 かつ ... かつ tn-1 - tn = 0 (mod T)

となる。最後の式は、Tが{ti - ti+1}の公約数であることを意味する。

逆に、Tが{ti - ti+1}の公約数であれば、条件を満たすyが存在する。(例えば y = (T - (t1 % T)) % T があり、実はこれが最小のy)

よってTの最大値は{ti - ti+1}の最大公約数。

require 'mathn'
gets.to_i.times do |c|
  n, *ts = gets.split.map{|s| s.to_i}
  g = (ts[1] - ts[0]).abs
  for i in (1..n-2)
    g = g.gcd((ts[i+1] - ts[i]).abs)
  end
  puts "Case ##{c + 1}: #{(g - ts[0] % g) % g}"
end

C. Theme Park

周期性を利用する。

もし、ある2つの時点で、コースターに乗る先頭のグループが同じなら、それ以降は全く同じ状況が起こる。先頭の選び方はN通りしかないので、高々N+1回でコースターに乗る先頭のグループが同じという状況が起こる。その後は、ループが１週したときの儲け * ループする回数 で一気に計算できる(余りの部分は適当になんとかする)。

#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;

long long g[1000];
int turn[1000];
long long money[1000];

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 0; t < T; ++t) {
    memset(turn, -1, sizeof(turn));
    memset(money, -1, sizeof(money));
    int R, k, N;
    scanf("%d%d%d", &R, &k, &N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", g+i);
    }
    int head = 0;
    long long m = 0;
    for (int i = 0; i < R; ) {
      if (turn[head] != -1) {
        long long period = i - turn[head];
        long long mouke = m - money[head];
        long long times = (R - i) / period;
        assert(mouke * times >= 0);
        assert(period * times >= 0);
        m += mouke * times;
        i += period * times;
        memset(turn, -1, sizeof(turn));
        memset(money, -1, sizeof(money));
      } else {
        money[head] = m;
        turn[head] = i;
        long long n_ride = 0, j;
        for (j = head; ; j = (j + 1) % N) {
          if (j == head && n_ride > 0)
            break;
          if (n_ride + g[j] > k)
            break;
          n_ride += g[j];
        }
        m += n_ride;
        head = j;
        ++i;
      }
      assert(m >= 0);
    }
    printf("Case #%d: %lld\n", t+1, m);
  }
}