Google Code Jam 2010 Qualification Round (After)

■問題A

2進カウンタをK回進めたとき，下位Nビットが全て1なら"ON"，そうでないなら"OFF"を出力せよ．

□解法B
ビット演算でクールにキメたかったのですが，あまり自信が無かったため，Kを2進文字列に直した後，下位Nビットが全て1であるか調べました．

import java.io.*;
public class A {
 public void a() throws Exception{
  BufferedReader br=new BufferedReader(new FileReader("C:\\A-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("C:\\A-large.out"));
  int T=Integer.parseInt(br.readLine());
  for(int i=0;i<T;i++){
   String[] s=br.readLine().split(" ");
   int N=Integer.parseInt(s[0]);
   int K=Integer.parseInt(s[1]);
   String t=toBS(K);
   boolean f=true;
   for(int j=t.length()-N;j<t.length();j++){
    if(j<0||t.charAt(j)!='1'){
     f=false;
     break;
    }
   }
   String ans="Case #"+(i+1)+": "+(f?"ON":"OFF");
   bw.write(ans);
   bw.newLine();
  }
  bw.close();
 }
 String toBS(int n){
  if(n==0)
   return "0";
  String s="";
  while(n!=0){
   s=n%2+s;
   n/=2;
  }
  return s;
 }
}

■問題B
長い文章でしたが，問題自体は↓．

maxy gcd(t1+y, t2+y, …, tN+y)となる最小のyを求めよ．

□解法B
まず，gcd(t₁+y, t₂+y, …, t_N+y)=mとします．
このとき，
m|t_i+y (1≦i≦N)
であるため，
m|(t_i+y)-(t_j+y) (1≦i, j≦N)
よって，
m|t_i-t_j (1≦i, j≦N)
ここで，
gcd_{1≦i, j≦N}(t_i-t_j)=n
とすれば，n=m(のはずです…)．
あとは，m|t₁+yとなるようにyを求めて((m-t₁)%mを計算する)終わり．

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

public class B {
 BigInteger calcY(int N,BigInteger[] t){
  Arrays.sort(t);

  LinkedList<BigInteger> list=new LinkedList<BigInteger>();
  for(int j=0;j<N-1;j++)
   for(int i=j+1;i<N;i++)
    list.add(t[j].subtract(t[i]));
  BigInteger gcd=list.get(0);
  for(BigInteger bi:list)
   gcd=bi.gcd(gcd);
   return gcd.subtract(t[0]).mod(gcd);
 }
 
 public void b() throws Exception{
  BufferedReader br=new BufferedReader(new FileReader("C:\\B-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("C:\\B-large.out"));
  int C=Integer.parseInt(br.readLine());
  for(int i=0;i<C;i++){
   String[] s=br.readLine().split(" ");
   int N=Integer.parseInt(s[0]);
   BigInteger[] t=new BigInteger[N];
   for(int j=0;j<N;j++)
    t[j]=new BigInteger(s[j+1]);
   BigInteger y=calcY(N,t);
   String ans="Case #"+(i+1)+": "+y;
   bw.write(ans);
   bw.newLine();
  }
  bw.close();
 }
}

■問題C

1人以上の客から構成されるグループがNグループある．1Euro/人とすると，k人乗りのローラーコースターをR回走らせた時，いくら稼げるか．

R=4，k=6，N=4として，グループ毎の人数を[1,4,2,1]と表すと，以下のようになります．

回数	乗っているグループ	待っているグループ	儲け
1	[1, 4]	[2, 1]	5
2	[2, 1, 1]	[4]	4
3	[4, 2]	[1, 1]	6
4	[1, 1 ,4]	[2]	6

□解法C
R>Nであれば，必ず，以前走らせた時と同じパターンが出てくるので，それを記憶しておき…としたのですが，コーディングをミスした模様．largeでエラー連発でした．

■結果

	A	B	C
small	○	○	○
large	○	○	×
point	33	33	10

76Point，2318位．

とりあえずは予選通過，ということで．