Google Code Jam 2011に登録完了

GCJ

Google Code Jam 2011


昨年に続いてGoogle Code Jamに参加します。昨年はQualification Roundは突破できましたが、Round 1ではSub-Round AからCまで全て参加しましたが尽く敗退し、苦い経験となっています。
昨年は競技プログラミングに出会い、PKU Online Judgeで鍛え、ACM-ICPCにも参加しました。最近はというと、チームでのシステム開発プロジェクトを経験したり、iPhoneアプリの開発をしたりと実務的なプログラミングが多く、競技プログラミングはご無沙汰気味でしたが、今回のGCJを機に少しずつ再開できたらと思います。プログラミングを好きになった原点なので！

過去問


GCJの公式サイトから過去問に取り組むことができます。少しでも競技プログラミングのカンを取り戻すために昨年のQualification Roundの問題に取り組みました。

Snapper Chain


指パッチンでON/OFFが切り替わるデバイスSnapperを使って電球を点灯させる問題。昨年は律儀にSnapperの動作をシュミレーションし、見事にLargeで落ちてしまいました。実は電源から連結されたSnapperのON/OFFの動作は二進数のビットそのもので、これに気づくとすごく簡単に、かつ高速なプログラムを書くことができます。実にGCJらしい問題だと思います。
昨年も載せましたがソースコードを再掲。

#include <cstdio>

using namespace std;

int T, N, K;

int main() {
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) {
    scanf("%d %d", &N, &K);
    int mask = (1<<N)-1;
    printf("Case #%d: %s\n", t, (mask&K)==mask?"ON":"OFF");
  }
}

Fair Warning


未だに問題の意味がわかりません。"slarboseconds"をググッても意味がわからずにパニクった記憶があります。どうやら最大公約数がポイントらしいということはわかるのですが、Largeでは10^50まで扱わなければならないため、私の場合はJavaでBigIntegerを使わなければなりませんでした。そういうこともあり手を付けていなかった問題。
Javaも良く分からないので今年は多倍長整数をどうしようと思っていたのですが、GCJでは使用するプログラミング言語に制約がないのでRubyを使ってみることにしました。Rubyも基礎程度しか知らないのですが、Javaよりも多倍長整数を扱いやすいので今年はこちらで行ってみます。

def calc_gcd(a, b)
  return b!=0?calc_gcd(b, a%b):a
end

class FairWarning
  def initialize
    @C = gets.chop.to_i
    puts @C
    for c in 1..@C
      a = gets.chop.split
      @N = a[0].to_i
      ts = []
      for i in 1..@N
        ts << a[i].to_i
      end
      result = solve(ts)
      print "Case ##{c}: #{result}\n"
    end
  end
  
  def solve ts
    ts = ts.sort
    ds = []
    for i in 0..ts.size-2
      d = ts[i+1]-ts[i]
      unless d == 0
        ds << d
      end
    end

    gcd = ds[0]
    for i in ds
      gcd = calc_gcd(gcd, i)
    end

    ret = ts[0] % gcd
    unless ret == 0
      ret = gcd - ret
    end

    return ret
  end
end

FairWarning.new

Theme Park


ジェットコースター大好きグループがN組いて、各グループはg1, ..., gN人。ジェットコースターの定員はk人で、同じグループの人がバラバラに乗るのは嫌がるし、順番を抜かされるのも嫌がる。乗り終わったグループは列の後ろに並ぶ。一日R回ジェットコースターを運行するとして、一日の売上は何ユーロか？（１ユーロ/人）
これも単純にシュミレーションをするとLargeでTLEになってしまう。グループの数は高々10^3なので、全グループについてそのグループを先頭としたときに乗れる人数とグループ数を予め計算しておけば良い。

#include <cstdio>

using namespace std;

int T, R, k, N;

int main() {
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) {
    scanf("%d %d %d", &R, &k, &N);
    int gs[N];
    for (int i = 0; i < N; ++i) {
      scanf("%d", &gs[i]);
    }
    int nps[N];
    int ngs[N];
    for (int i = 0; i < N; ++i) {
      int np = 0, ng = 0;
      for (int j = 0; j < N; ++j) {
	if (np + gs[(i+j)%N] > k) break;
	np += gs[(i+j)%N];
	++ng;
      }	
      nps[i] = np;
      ngs[i] = ng;
    }
    int pos = 0;
    long euros = 0;
    for (int r = 0; r < R; ++r) {
      euros += nps[pos];
      pos = (pos+ngs[pos])%N;
    }
    printf("Case #%d: %ld\n", t, euros);
  }
}

昨年よりも圧倒的に練習が足りないですが、とりあえず予選通過はしたいと思います！