Google Code Jam 2010 Qualification Round

参加しました．
先に言い訳をしておくと，酔った頭で寝起きに解いた上に，
久しぶりのプログラミングだったのでぼろぼろでした．

Google Code Jam
Code Jam Statistics (2016)

ちゃんと問題を読まずに10^8だから32bit-intでいけるギリギリなんだなと思ってたら，
思いっきりあふれて答えがマイナスになり，あせって直しましたが一ヶ所直し忘れwrong answerになりました．
というわけで，76点．

とりあえず解答をみやすく整形したものを載せておく．
本番提出したものは，昔作った入出力用のテンプレートを作ったので読みにくいです．
実行時に標準入出力先を指定しなくて済むので楽なだけ．

Snapper Chain

結局はKの2進法表記の下位N bitを左右反転させたものと各snapperのON-OFFが対応します．
なので，K%(1<

import java.util.*;
public class A {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int cases=1;cases<=n;++cases){
            int N = sc.nextInt();
            int K = sc.nextInt();
            System.out.println("Case #"+cases+": "+((K%(1<<N)==(1<<N)-1)?"ON":"OFF"));
        }
    }
}

Fair Warning

a_1

import static java.util.Arrays.*;
import java.util.*;
import java.math.*;
public class B {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int cases=1;cases<=n;++cases){
            int N = sc.nextInt();
            BigInteger[] ts = new BigInteger[N];
            for(int i=0;i<N;++i)ts[i]=sc.nextBigInteger();
            sort(ts);
            BigInteger gcd = ts[1].subtract(ts[0]);
            for(int i=2;i<N;++i)gcd = gcd.gcd(ts[i].subtract(ts[0]));
            BigInteger ans=gcd.subtract(ts[0].mod(gcd)).mod(gcd);
            System.out.println("Case #"+cases+": "+ans);
        }
    }
}

Theme Park

ジェットコースターで100000000000000000ユーロ儲けるかもしれないと皮算用している人のため問題です．
組み合わせがどのグループから乗り始めるかの組み合わせがN通りしかないので，そのうちループします．
ループ部分をまとめて処理すれば終わり．必ずlongで計算すること．

import java.util.*;
public class C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int cases=1;cases<=n;++cases){
            long R = sc.nextLong();
            long k = sc.nextLong();
            int N = sc.nextInt();
            long[] g = new long[N];
            for(int i=0;i<N;++i)g[i]=sc.nextInt();
            //grouping
            long[] size = new long[N];
            int[] next = new int[N];
            for(int i=0;i<N;++i){
                int j=i;
                while(size[i]+g[j]<=k){
                    size[i]+=g[j];
                    j=(j+1)%N;
                    if(j==i)break;
                }
                next[i]=j;
            }
            //loop detecting
            int cs = 0;
            int initL = 0;
            long initC = 0;
            boolean[] check = new boolean[N];
            while(!check[cs]){
                initL++;
                initC+=size[cs];
                check[cs]=true;
                cs=next[cs];
            }

            int css = cs;
            long sum = 0;
            ArrayList<Long> loop = new ArrayList<Long>();
            while(true){
                sum+=size[css];
                loop.add(size[css]);
                css=next[css];
                if(cs==css)break;
            }
            long ans = 0;
            if(R<=initL){
                int j=0;
                for(int i=0;i<R;++i){
                    ans+=size[j];
                    j=next[j];
                }
            }else{
                ans+=initC;
                ans+=(R-initL)/loop.size()*sum;
                for(int i=0;i<(R-initL)%loop.size();++i)ans+=loop.get(i);
            }
            System.out.println("Case #"+cases+": "+ans);
        }
    }
}

実際はループ検出などしなくても，1億回程度なので15秒ほどで解けるため次のようなプログラムで十分．

import java.util.*;
public class C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int cases=1;cases<=n;++cases){
            long R = sc.nextLong();
            long k = sc.nextLong();
            int N = sc.nextInt();
            long[] g = new long[N];
            for(int i=0;i<N;++i)g[i]=sc.nextInt();

            long[] size = new long[N];
            int[] next = new int[N];
            for(int i=0;i<N;++i){
                int j=i;
                while(size[i]+g[j]<=k){
                    size[i]+=g[j];
                    j=(j+1)%N;
                    if(j==i)break;
                }
                next[i]=j;
            }
            long ans = 0;
            int j=0;
            for(int i=0;i<R;++i){
                ans+=size[j];
                j=next[j];
            }
            System.out.println("Case #"+cases+": "+ans);
        }                                                                                                                                                         
    }
}