Google Code Jam 2010 Qualification Round (After)

■問題A

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

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

view plainprint?

1. import java.io.*;  
2. public class A {  
3.  public void a() throws Exception{  
4.   BufferedReader br=new BufferedReader(new FileReader("C:\\A-large.in"));  
5.   BufferedWriter bw=new BufferedWriter(new FileWriter("C:\\A-large.out"));  
6.   int T=Integer.parseInt(br.readLine());  
7.   for(int i=0;i<T;i++){  
8.    String[] s=br.readLine().split(" ");  
9.    int N=Integer.parseInt(s[0]);  
10.    int K=Integer.parseInt(s[1]);  
11.    String t=toBS(K);  
12.    boolean f=true;  
13.    for(int j=t.length()-N;j<t.length();j++){  
14.     if(j<0||t.charAt(j)!='1'){  
15.      f=false;  
16.      break;  
17.     }  
18.    }  
19.    String ans="Case #"+(i+1)+": "+(f?"ON":"OFF");  
20.    bw.write(ans);  
21.    bw.newLine();  
22.   }  
23.   bw.close();  
24.  }  
25.  String toBS(int n){  
26.   if(n==0)  
27.    return "0";  
28.   String s="";  
29.   while(n!=0){  
30.    s=n%2+s;  
31.    n/=2;  
32.   }  
33.   return s;  
34.  }  
35. }  

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を計算する)終わり．

view plainprint?

1. import java.io.*;  
2. import java.math.*;  
3. import java.util.*;  
4.   
5. public class B {  
6.  BigInteger calcY(int N,BigInteger[] t){  
7.   Arrays.sort(t);  
8.   
9.   LinkedList<BigInteger> list=new LinkedList<BigInteger>();  
10.   for(int j=0;j<N-1;j++)  
11.    for(int i=j+1;i<N;i++)  
12.     list.add(t[j].subtract(t[i]));  
13.   BigInteger gcd=list.get(0);  
14.   for(BigInteger bi:list)  
15.    gcd=bi.gcd(gcd);  
16.    return gcd.subtract(t[0]).mod(gcd);  
17.  }  
18.    
19.  public void b() throws Exception{  
20.   BufferedReader br=new BufferedReader(new FileReader("C:\\B-large.in"));  
21.   BufferedWriter bw=new BufferedWriter(new FileWriter("C:\\B-large.out"));  
22.   int C=Integer.parseInt(br.readLine());  
23.   for(int i=0;i<C;i++){  
24.    String[] s=br.readLine().split(" ");  
25.    int N=Integer.parseInt(s[0]);  
26.    BigInteger[] t=new BigInteger[N];  
27.    for(int j=0;j<N;j++)  
28.     t[j]=new BigInteger(s[j+1]);  
29.    BigInteger y=calcY(N,t);  
30.    String ans="Case #"+(i+1)+": "+y;  
31.    bw.write(ans);  
32.    bw.newLine();  
33.   }  
34.   bw.close();  
35.  }  
36. }  

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位．

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