Google Code Jam 2011 Qualification Round

Google Code Jam

今年も調子に乗ってGCJに参戦。
今回は、何となくJavaで挑戦してみました。(Round1からは通常通りC++の予定)

  • -

A : Bot Trust

問題：2台のロボットでボタンを決められた順に押すための最短時間を求める問題。

  • 各ロボットはボタンを押したら次に押すボタンに移動する。
  • 移動したら相手がボタンを押し終わるまで待機。
  • という感じで適当にシミュレーションして提出してみた。

B : Magicka

問題：魔法を使ったときのelement listの中身をシミュレートする問題。

  • 問題文の読解にやたら時間がかかった。
    • 読めなすぎて20分近く悩んだ挙句、先にCとDをやったくらいのレベル。
  • 読めてしまえばやるだけなので、余裕。
    • かと思いきや派手に読み間違えてて4WAを記録してしまった。
    • (´・ω・｀)
  • 11，12話だけを見た呪いかと思ってたけど、よく見たら違った。

C : Candy Splitting

問題：N個の整数を2つの空でない集合に分け、それぞれのxorが等しくなるようにする。このような分け方をしたときの、片側の総和の最大値を求める問題。

  • とりあえず、同じ数のxorは0なので、分けれるなら全部のxorが0になる。
  • で、全部のxorが0ならどう分けてもそれぞれのxorをとった結果は等しくなる。
  • ので、(N個の整数の総和-最小の数) が答え。
  • 予選で一番楽だった問題。

D : GoroSort

問題：数列の任意の部分集合をランダムに並び替える操作を繰り返して、ソートが完了するまでの操作回数の期待値を求める。

  • 場所があってる数は並び替え操作から外す
  • という戦略で、n個全部の位置が違うときの期待値e(n)を求めてみることにした。
  • 式を立ててみたら、
    • e(2) = 1/2 * e(2) + 1 → e(2) = 2
    • e(3) = 2/6 * e(3) + 3/6 * e(2) + 1 → e(3) = 3
  • あれ？と思ってプログラムを書き、e(n)=n が成り立つことを n≦11 で確かめた。
    • e(n)=nなら、適当に循環を探して操作を分割しても期待値は変わらない。
  • 少なくともsmall(n≦10)は通るので、e(n)=nを信じて特攻してみた。
  • あとで式を立ててマジメに計算したらe(n)=nで合ってたので安心した。
  • -

全部通っていたので、まずは一安心というところ。
Bに時間がかかりすぎてしまったので、次に向けて反省。


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

A : Bot Trust

import java.io.*;
import java.util.*;

public class GCJ2011QualA{
    void solve(){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int testCase=1;testCase<=T;testCase++){
            int N = sc.nextInt();
            int oT = 0, bT = 0;
            int oP = 1, bP = 1;
            for(int i=0;i<N;i++){
                char[] c = sc.next().toCharArray();
                int pos = sc.nextInt();
                if(c[0] == 'O'){
                    oT = Math.max(oT+Math.abs(pos-oP), bT)+1;
                    oP = pos;
                } else {
                    bT = Math.max(bT+Math.abs(pos-bP), oT)+1;
                    bP = pos;
                }
            }
            System.out.println("Case #"+testCase+": "+Math.max(bT, oT));
        }
    }
    public static void main(String args[]){
        new GCJ2011QualA().solve();
    }
}

B : Magicka

import java.io.*;
import java.util.*;

public class GCJ2011QualB{
    void solve(){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int QB=1;QB<=T;QB++){
            int C = sc.nextInt();
            char[][] cb = new char[C][3];
            for(int i=0;i<C;i++) cb[i] = sc.next().toCharArray();
            int D = sc.nextInt();
            char[][] op = new char[D][3];
            for(int i=0;i<D;i++) op[i] = sc.next().toCharArray();
            int N = sc.nextInt();
            char[] spell = sc.next().toCharArray();
            char[] res   = new char[T];
            int size = 0;
            for(int i=0;i<N;i++){
                res[size++] = spell[i];
                if(size>=2){
                    for(int j=0;j<C;j++){
                        if((res[size-1]==cb[j][0]&&res[size-2]==cb[j][1]) ||
                           (res[size-2]==cb[j][0]&&res[size-1]==cb[j][1])){
                            res[size-2] = cb[j][2];
                            size--;
                            break;
                        }
                    }
                }
                for(int j=0;j<size-1;j++){
                    for(int k=0;k<D;k++){
                        if((res[j]==op[k][0]&&res[size-1]==op[k][1]) ||
                           (res[size-1]==op[k][0]&&res[j]==op[k][1])){
                            size = 0;
                            break;
                        }
                    }
                }
            }
            System.out.print("Case #"+QB+": [");
            if(size > 0){
                for(int i=0;i+1<size;i++) System.out.print(res[i] + ", ");
                System.out.println(res[size-1] + "]");
            } else {
                System.out.println("]");
            }
        }
    }
    public static void main(String args[]){
        new GCJ2011QualB().solve();
    }
}

C : Candy Splitting

import java.io.*;
import java.util.*;

public class GCJ2011QualC{
    void solve(){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int testCase=1;testCase<=T;testCase++){
            int N = sc.nextInt();
            int sum = 0, xor = 0, m = 10000000;
            for(int i=0;i<N;i++){
                int C = sc.nextInt();
                sum += C;
                xor ^= C;
                m = Math.min(m, C);
            }
            System.out.print("Case #"+testCase+": ");
            if(xor != 0) System.out.println("NO");
            else         System.out.println(sum-m);
        }
    }
    public static void main(String args[]){
        new GCJ2011QualC().solve();
    }
}

D : GoroSort

import java.io.*;
import java.util.*;

public class GCJ2011QualD{
    void solve(){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int testCase=1;testCase<=T;testCase++){
            int N = sc.nextInt();
            int res = 0;
            for(int i=1;i<=N;i++)
                if(i!=sc.nextInt()) res++;
            System.out.println("Case #"+testCase+": "+res);
        }
    }
    public static void main(String args[]){
        new GCJ2011QualD().solve();
    }
}