Google Code Jam 2010 Qualification Round

Google Code Jamに挑戦してみる。
開催を知ったのは，Qualification Roundの前日でしたが・・・。

A : Snapper Chain

問題：長さNのビット列があって，初期状態では全ビットが0。1度のsnapでは，先頭から続く1が全て0となり，続く1つの0が1になる。Nビット全てが1となっている時を"ON"，その他を"OFF"とするとき，K回のsnap後の"ON"，"OFF"を判定しなさい。

英語読めねーと思ってしばし焦る。
冷静に考えると，1回のsnapって要するに1を加えるだけの操作。
よって，2^N-1回目にONになった後は2^N回ごとにONになる。

B : Fair Warning

問題：N個の正整数t[i]に対し，t[i]+Tの最大公約数を最大化するような最小の非負整数Tを返す

最大になるときの最大公約数Gはt[i]同士の差の最大公約数を計算すれば良いとして。
それさえ出ればt[0]をGの倍数にするようなTを求めれば良いのだけど。
この問題の鬼門はt[i]が最大で10の50乗という事。64bit整数でも無理。

最大公約数なら引き算だけあれば良いか・・・と思い，c++で多倍長整数の実装をする事に。
が，引き算だけで長大数のgcdとか時間的に無理なことに気づく。
仕方ないのでjavaの勉強を開始し，頑張って実装した。

サンプルの2番が通らないコードを提出し，2WA。
答え合わせくらいちゃんとやれよ自分・・・。

C : Theme Park

問題：N個のグループがジェットコースターに並んでいる。1度にK人までが乗れて，乗ったグループは前の順番を保ったまま後ろに並びなおす。R回の運行で乗れる人数の合計は？

Nが最大1000，Rが最大1億なので単純なシミュレーションはアウト。
並び順は保存されるので，各グループが先頭だった時にどのグループまで乗れるかは一意に決まる。
それをテーブルに持っておけばO(R)で計算できる。
周期性を利用してO(N)まで攻める事も出来そうだけど，面倒なのでO(R)で。

3問ともsmallもlargeも通ってたのでたぶん通過。
サンプルで間違ってるのを見落としたのが，とにかくショック。

以下，書いたコード一覧。

A : Snapper Chain

#include <iostream>

using namespace std;

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N, K; cin >> N >> K;
        cout << "Case #" << test << ": " << (K%(1<<N) == (1<<N)-1 ? "ON" : "OFF") << endl; 
    }
}

B : Fair Warning

import java.util.*;
import java.math.*;

public class B2{
    public static void main(String args[]){
        Scanner s = new Scanner(System.in);
        int T = s.nextInt();
        int test;
        for(test=1;test<=T;test++){
            int i, j;
            int N = s.nextInt();
            Set<BigInteger> S = new HashSet<BigInteger>();
            for(i=0;i<N;i++){
                S.add(s.nextBigInteger());
            }
            BigInteger[] num = new BigInteger[S.size()];
            S.toArray(num);
            Arrays.sort(num);
            BigInteger g = num[1].subtract(num[0]);
            for(i=2;i<S.size();i++){
                g = g.gcd(num[i].subtract(num[0]));
            }
            if(num[0].mod(g).compareTo(BigInteger.ZERO) == 0)
                g = BigInteger.ZERO;
            else
                g = g.subtract(num[0].mod(g));
            System.out.println("Case #" + test + ": " + g);
        }
    }
}

C : Theme Park

#include <iostream>

using namespace std;

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int R, K, N; cin >> R >> K >> N;
        long long sum = 0;
        int ride[1000];
        int pass[1000];
        int next[1000];
        for(int i=0;i<N;i++){
            cin >> ride[i];
            sum += ride[i];
        }
        if(sum <= K){
            printf("Case #%d: %lld\n", test, sum*R);
            continue;
        }
        for(int i=0;i<N;i++){
            int cur = 0;
            for(int j=0;j<N;j++){
                if(cur+ride[(i+j)%N] > K){
                    pass[i] = cur;
                    next[i] = (i+j)%N;
                    break;
                }
                cur += ride[(i+j)%N];
            }
        }
        long long ans = 0;
        int idx = 0;
        for(int i=0;i<R;i++){
            ans += pass[idx];
            idx = next[idx];
        }
        printf("Case #%d: %lld\n", test, ans);
    }
}