セルオートマトン #29 ルール27

ルール27
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	□	■	■

Fig.1 rule27

Google Code Jam 2010 Round 1C

1Bで1000位以内に入れなかったので再び挑戦．

■問題A

ビルとビルの間に複数のロープを張っていく．双方のビルに張るロープの位置が与えられた時，何箇所が交差するか．

□解法A
これは見た瞬間解法が分かったので，small，large共に開始10分以内に提出できました．

view plainprint?

1. import java.io.*;  
2. import java.util.*;  
3. public class A {  
4.  int cal(int n,int[] a,int[] b){  
5.   int res=0;  
6.   for(int j=0;j<n-1;j++)  
7.    for(int i=j+1;i<n;i++)  
8.     if((a[j]-a[i])*(b[j]-b[i])<0)  
9.      res++;  
10.   return res;  
11.  }  
12.  void a() throws Exception{  
13.   Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.in"));  
14.   BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.out"));  
15.   int T=sc.nextInt();  
16.   for(int k=0;k<T;k++){  
17.    int N=sc.nextInt();  
18.    int[] a=new int[N];  
19.    int[] b=new int[N];  
20.    for(int i=0;i<N;i++){  
21.     a[i]=sc.nextInt();  
22.     b[i]=sc.nextInt();  
23.    }  
24.    int ans=cal(N,a,b);  
25.    System.out.println("Case #"+(k+1)+": "+ans);  
26.    bw.write("Case #"+(k+1)+": "+ans);  
27.    bw.newLine();  
28.   }  
29.   bw.close();  
30.  }  
31. }  

import java.io.*;
import java.util.*;
public class A {
 int cal(int n,int[] a,int[] b){
  int res=0;
  for(int j=0;j<n-1;j++)
   for(int i=j+1;i<n;i++)
    if((a[j]-a[i])*(b[j]-b[i])<0)
     res++;
  return res;
 }
 void a() throws Exception{
  Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1c\\a\\A-large.out"));
  int T=sc.nextInt();
  for(int k=0;k<T;k++){
   int N=sc.nextInt();
   int[] a=new int[N];
   int[] b=new int[N];
   for(int i=0;i<N;i++){
    a[i]=sc.nextInt();
    b[i]=sc.nextInt();
   }
   int ans=cal(N,a,b);
   System.out.println("Case #"+(k+1)+": "+ans);
   bw.write("Case #"+(k+1)+": "+ans);
   bw.newLine();
  }
  bw.close();
 }
}

■問題B
問題の内容がさっぱり分かりませんでした…．

□解法B
省略．

■問題C

白と黒のタイルで構成されたボードからチェスボード(白と黒の市松模様)を切り出していく．出来るだけ大きいチェスボードから切り出していった時，どの大きさのものが幾つ出来るか．

□解法C
コードが物凄く汚い&smallしか解けないので省略．

■結果

	A	B	C
small	○(9)	×(14)	○(18)
large	○(13)	×(22)	×(24)
point	22	0	18

40Point，1072位．

というわけで敗退．40Pointでも，早く解けた人はRound 2に進出出来たので，時間差といえば時間差です．が，もう少し，頭の切り替えが早ければ，1000以内に入れたかもしれません．

Google Code Jam 2010 Round 1B

■問題A

既に作られているディレクトリ構造と，これから作ろうとしているディレクトリ構造が与えられる．mkdirコマンドは何回実行する必要があるか．

□解法A
実装ゲー．ちまちましたミスでかなり手間取ってしまいました．

view plainprint?

1. import java.io.*;  
2. import java.util.*;  
3.   
4. public class A {  
5.   
6.  class Node{  
7.   HashMap<String, Node> children=new HashMap<String, Node>();  
8.  }  
9.   
10.  long cal(int N, int M, String[] exist, String[] create){  
11.   Node root=new Node();  
12.     
13.   for(int i=0;i<N;i++){  
14.    String[] s=exist[i].split("/");  
15.    Node node=root;  
16.    for(int k=1;k<s.length;k++){  
17.     if(!node.children.containsKey(s[k]))  
18.      node.children.put(s[k], new Node());  
19.     node=node.children.get(s[k]);  
20.    }  
21.   }  
22.     
23.   long ret=0;  
24.   for(int i=0;i<M;i++){  
25.    String[] s=create[i].split("/");  
26.    Node node=root;  
27.    for(int k=1;k<s.length;k++){  
28.     if(!node.children.containsKey(s[k])){  
29.      ret++;  
30.      node.children.put(s[k], new Node());  
31.     }  
32.     node=node.children.get(s[k]);  
33.    }  
34.   }  
35.     
36.   return ret;  
37.  }  
38.    
39.  void a() throws Exception{  
40.   Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.in"));  
41.   BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.out"));  
42.   
43.   int T=sc.nextInt();  
44.   for(int k=0;k<T;k++){  
45.    int N=sc.nextInt();  
46.    int M=sc.nextInt();  
47.    sc.nextLine();  
48.      
49.    String[] exist=new String[N];  
50.    for(int i=0;i<N;i++)  
51.     exist[i]=sc.nextLine();  
52.      
53.    String[] create=new String[M];  
54.    for(int i=0;i<M;i++)  
55.     create[i]=sc.nextLine();  
56.      
57.    long ans=cal(N,M,exist,create);  
58.    System.out.println("Case #"+(k+1)+": "+ans);  
59.    bw.write("Case #"+(k+1)+": "+ans);  
60.    bw.newLine();  
61.   }  
62.   bw.close();  
63.  }  
64. }  

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

public class A {

 class Node{
  HashMap<String, Node> children=new HashMap<String, Node>();
 }

 long cal(int N, int M, String[] exist, String[] create){
  Node root=new Node();
  
  for(int i=0;i<N;i++){
   String[] s=exist[i].split("/");
   Node node=root;
   for(int k=1;k<s.length;k++){
    if(!node.children.containsKey(s[k]))
     node.children.put(s[k], new Node());
    node=node.children.get(s[k]);
   }
  }
  
  long ret=0;
  for(int i=0;i<M;i++){
   String[] s=create[i].split("/");
   Node node=root;
   for(int k=1;k<s.length;k++){
    if(!node.children.containsKey(s[k])){
     ret++;
     node.children.put(s[k], new Node());
    }
    node=node.children.get(s[k]);
   }
  }
  
  return ret;
 }
 
 void a() throws Exception{
  Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\a\\A-large.out"));

  int T=sc.nextInt();
  for(int k=0;k<T;k++){
   int N=sc.nextInt();
   int M=sc.nextInt();
   sc.nextLine();
   
   String[] exist=new String[N];
   for(int i=0;i<N;i++)
    exist[i]=sc.nextLine();
   
   String[] create=new String[M];
   for(int i=0;i<M;i++)
    create[i]=sc.nextLine();
   
   long ans=cal(N,M,exist,create);
   System.out.println("Case #"+(k+1)+": "+ans);
   bw.write("Case #"+(k+1)+": "+ans);
   bw.newLine();
  }
  bw.close();
 }
}

■問題B

沢山のヒヨコちゃんがレール上にいる．それぞれのヒヨコはある方向に走っており，後方のヒヨコちゃんは，前方のヒヨコちゃんに追いついてしまったら，前方のヒヨコちゃんと同じ速度に減速する．また，クレーンを使って隣り合う2匹のヒヨコちゃんを交換することが出来る．N匹のヒヨコに対し，初期位置xi[m]と速度vi[m/s]が与えられる．K(≦N)匹のヒヨコがT[s]以内でB[m]の地点に到達するように，クレーンでヒヨコを移動させた時，その最小回数はいくらか．

□解法B
ヒヨコ?クレーン?といった感じで，問題文を理解するのにかなりの時間が掛かってしまいました．分かった後はこれまた実装ゲー．

view plainprint?

1. import java.io.*;  
2. import java.util.*;  
3.   
4. public class B {  
5.   
6.  String cal(int N,int K,long B,int T,int[] x,int[] v){  
7.   boolean[] barn=new boolean[N];  
8.   int nBarn=0;  
9.   for(int i=0;i<N;i++){  
10.    int p=x[i]+v[i]*T;  
11.    if(p>=B)  
12.     nBarn++;  
13.    barn[i]=p>=B;  
14.   }  
15.   if(nBarn<K)  
16.    return "IMPOSSIBLE";  
17.   
18.   int pick=0;  
19.   int j=N;  
20.   for(int k=0;k<K;k++){  
21.    while(!barn[--j]);  
22.    for(int i=j;i+1<N&&!barn[i+1];i++){  
23.     boolean f=barn[i];  
24.     barn[i]=barn[i+1];  
25.     barn[i+1]=f;  
26.     pick++;  
27.    }  
28.   }  
29.     
30.   return ""+pick;  
31.  }  
32.    
33.  void a() throws Exception{  
34.   Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.in"));  
35.   BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.out"));  
36.   
37.   int C=sc.nextInt();  
38.   for(int k=0;k<C;k++){  
39.    int N=sc.nextInt();  
40.    int K=sc.nextInt();  
41.    long B=sc.nextLong();  
42.    int T=sc.nextInt();  
43.    int[] x=new int[N];  
44.    int[] v=new int[N];  
45.   
46.    for(int i=0;i<N;i++)  
47.     x[i]=sc.nextInt();  
48.    for(int i=0;i<N;i++)  
49.     v[i]=sc.nextInt();  
50.      
51.    String ans=cal(N,K,B,T,x,v);  
52.    System.out.println("Case #"+(k+1)+": "+ans);  
53.    bw.write("Case #"+(k+1)+": "+ans);  
54.    bw.newLine();  
55.   }  
56.   bw.close();  
57.  }  
58.    
59. }  

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

public class B {

 String cal(int N,int K,long B,int T,int[] x,int[] v){
  boolean[] barn=new boolean[N];
  int nBarn=0;
  for(int i=0;i<N;i++){
   int p=x[i]+v[i]*T;
   if(p>=B)
    nBarn++;
   barn[i]=p>=B;
  }
  if(nBarn<K)
   return "IMPOSSIBLE";

  int pick=0;
  int j=N;
  for(int k=0;k<K;k++){
   while(!barn[--j]);
   for(int i=j;i+1<N&&!barn[i+1];i++){
    boolean f=barn[i];
    barn[i]=barn[i+1];
    barn[i+1]=f;
    pick++;
   }
  }
  
  return ""+pick;
 }
 
 void a() throws Exception{
  Scanner sc=new Scanner(new FileReader("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.in"));
  BufferedWriter bw=new BufferedWriter(new FileWriter("D:\\google_code_jam\\gcj2010\\round1b\\b\\B-large.out"));

  int C=sc.nextInt();
  for(int k=0;k<C;k++){
   int N=sc.nextInt();
   int K=sc.nextInt();
   long B=sc.nextLong();
   int T=sc.nextInt();
   int[] x=new int[N];
   int[] v=new int[N];

   for(int i=0;i<N;i++)
    x[i]=sc.nextInt();
   for(int i=0;i<N;i++)
    v[i]=sc.nextInt();
   
   String ans=cal(N,K,B,T,x,v);
   System.out.println("Case #"+(k+1)+": "+ans);
   bw.write("Case #"+(k+1)+": "+ans);
   bw.newLine();
  }
  bw.close();
 }
 
}

■問題C

a1, …, ak=nという数列がある．nはk番目，kはi番目，iはj番目，…という操作の結果，最終的にa1は1番目，となるような数列はいくつあるか．与えられる数はnのみ．

□解法C
コーディングが間に合わず．

■結果

	A	B	C
small	○(12)	○(13)	×(14)
large	○(14)	○(17)	×(30)
point	26	30	0

56Point，1257位．

1000位以内に入れなかったのでRound2に進めず…．18:00からのRound1Cで1000位以内に入れなかったら敗退．

Project Euler

problem 57
problem 81
problem 99

セルオートマトン #27 ルール25

ルール25
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	□	□	■

Fig.1 rule25

マージソート

何となく作りたくなったので，マージソート．

■コード

view plainprint?

1. /** Marge sort(マージソート) */  
2. public void margeSort(int[] a){  
3.  int n=a.length;  
4.  if(n==1) return;  
5.  // b.length+c.length=a.length  
6.  int[] b=new int[n/2];  
7.  int[] c=new int[n-n/2];  
8.  System.arraycopy(a, 0, b, 0, b.length);  
9.  System.arraycopy(a, n/2, c, 0, c.length);  
10.  margeSort(b);  
11.  margeSort(c);  
12.  // ソートされたbとcをaにマージ  
13.  for(int i=0, j=0, k=0;i<n;i++)  
14.   if(k==c.length)  
15.    a[i]=b[j++];  
16.   else if(j==b.length)  
17.    a[i]=c[k++];  
18.   else if(b[j]<c[k])  
19.    a[i]=b[j++];  
20.   else  
21.    a[i]=c[k++];  
22. }  

/** Marge sort(マージソート) */
public void margeSort(int[] a){
 int n=a.length;
 if(n==1) return;
 // b.length+c.length=a.length
 int[] b=new int[n/2];
 int[] c=new int[n-n/2];
 System.arraycopy(a, 0, b, 0, b.length);
 System.arraycopy(a, n/2, c, 0, c.length);
 margeSort(b);
 margeSort(c);
 // ソートされたbとcをaにマージ
 for(int i=0, j=0, k=0;i<n;i++)
  if(k==c.length)
   a[i]=b[j++];
  else if(j==b.length)
   a[i]=c[k++];
  else if(b[j]<c[k])
   a[i]=b[j++];
  else
   a[i]=c[k++];
}

■特徴
・分割統治法を用いたソートアルゴリズム
・最悪計算量O(nlogn)
・安定ソートである

■原理
ある配列(数列)aとbが以下であるとします．

a1, …, am

b1, …, bn

この時，

ai<=ai+1

bj<=bj+1

とすれば，つまり，aもbもソートされているとすれば，それらをマージした以下の配列(数列)cが作れる．

c1, …, cm+n

これを再帰的に適用します．

■適用例
8,3,4,6,2,5,7,1

まずは，"分割"します．

8

3

4

6

2

5

7

1

8

3

4

6

2

5

7

1

8

3

4

6

2

5

7

1

8

3

4

6

2

5

7

1

配列の要素が一つになるまで"分割"しました．要素数が1の配列が"ソートされている事"は，明らかですので，ここからはソートされている配列を"統治"していきます．

3

8

4

6

2

5

1

7

ここで，要素数が2の配列が4つ出来ましたが，それぞれソートされています．

3

4

6

8

1

2

5

7

1

2

3

4

5

6

7

8

というわけでゴール．正しくソートされました．

J #2 q:

Jには，素因数分解を行ってくれる素晴らしい動詞があります．

q: Prime Factors / Prime Exponents

こんな感じ

   q: 700
2 2 5 5 7
   2 q: 700
2 0
   10 q: 700
2 0 2 1 0 0 0 0 0 0
   _ q: 700
2 0 2 1
   __ q: 700
2 5 7
2 2 1

・q: 700
700の約数を並べたものをアレイとして返します(700=2²5²7¹)．
・2 q: 700
700 = Π_k p_k^r_k(p_kはk番目の素数)としたとき，r_kを2個並べたものを返します．10 q: 700も同様です．
・_ q: 700
上のr_kを必要最低限だけ並べたものを返します．上の例でr_iは，2 0 2 1 0 0 0 0 …であり，2 0 2 1以降は全て0となるため，2 0 2 1となります．
・__ q: 700
r_k≠0であるp_kとr_kを並べたテーブルを返します．

動詞q:を使うと，オイラーのφ関数を簡潔に記述することができます．

φ(n)は，1~nまでの自然数に対しnと互いに素なものの個数を表し，
n = Π_k p_k^r_k
としたとき(p_kはk番目の素数)，
φ(n) = n Π_k (1 - 1/p_k)
が成立します．

Euler’s totient function(オイラーのφ関数)

   totient=: * -.@%@~.&.q:
   totient 700
240

まず，totientを構成する動詞，副詞について説明します．

定義
x y
(動詞への)引数
m n
名詞
u v
動詞
f g h
動詞

動詞
x * y
x*y
Times
乗算(二項演算)
-. y
1-y
Complement
補数(単項演算)
% y
1/y
Reciprocal
逆数(単項演算)
~. y
-
Nub
重複要素削除(単項演算)
q: y
-
Prime Factors
素因数分解(単項演算)

副詞
@
u@v y ⇔ u v y
Atop
&.
u&.v y ⇔ vi u v y (viはvの逆演算)
Under

これより，

-.@%@~.

は，(厳密には演算の順序が)以下のようになります．

-. % ~.

また，

-.@%@~.&.q: y

は，以下のようになります．

q:の逆演算 -. % ~. q: y

結果として，

(* -.@%@~.&.q:) y

は，(Hookが適用され)以下のようになります．

y * (q:の逆演算 -. % ~. q:) y

実際に順を追ってみていきましょう．
y=700とすると，
1. q:でyを素因数分解．
2 2 5 5 7
2. ~.で重複要素を削除．
2 5 7
3. %でそれぞれの要素について逆数をとる．
0.5 0.2 0.142857
4. -.で補数をとる．
0.5 0.8 0.857143
5. q:の逆演算を適用．q:の逆演算は(多分)アレイの要素全てを掛け合わせたものです．
0.342857
ここまでで，(q:の逆演算 -. % ~. q:) yが計算できました．Π_k (1-1/p_k)と同じ計算をしているのが分かるでしょうか?
6. y=700 に ((q:の逆演算 -. % ~. q:) y)=0.342857をかける．
240

というわけで．Jであらわしたφ関数は，
φ(n) = n Π_k (1-1/p_k)
を忠実に計算していたのです．

まだJを始めて間もないですので，間違いがありましたら指摘して下さると助かります．

PKU Judge Online

1007

PKU Judge Online

1000
1002
1003
1004
1005

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

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

Google Code Jam 2010 Qualification Round (Before)

ついにやってきました．Google Code Jam 2010．
Google Code Jam

Google Code Jamとは，Google主催のプログラミングコンテストで，2003年から年1回開催されます．
実は，前回も挑戦したのですが，全く歯が立ちませんでした．というわけで，今回は予選通過を目標にしました．

予選のQualification Roundは，日本時間で5/8AM8:00より24時間でしたので解いてきました．
とりあえず，A，Bに関してsmall，large共に提出できました(Cではlarge失敗)．今回は，A，B，Cの内small，large共に正答しているものが一つでもあれば予選通過になります．

結果が出次第，詳細を追って報告します．

セルオートマトン #26 ルール24

ルール24
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	■	□	□	□

Fig.1 rule24

TopCoder 練習

TheMoviesLevelOneDivOne(SRM469 DIV1 Easy)

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. public class TheMoviesLevelOneDivOne {  
5.  public long find(int n, int m, int[] row, int[] seat) {  
6.   long ret=(long)(m-1)*n;  
7.   int len=row.length;  
8.   for(int j=0;j<len;j++){  
9.    if(seat[j]>1)  
10.     ret--;  
11.    if(seat[j]<m)  
12.     ret--;  
13.    for(int i=0;i<len;i++)  
14.     if((i!=j) && (row[i]==row[j]) && (seat[i]==seat[j]+1))  
15.      ret++;  
16.   }  
17.   return ret;  
18.  }  
19. }  

import java.util.*;
import java.lang.*;
import java.math.*;
public class TheMoviesLevelOneDivOne {
 public long find(int n, int m, int[] row, int[] seat) {
  long ret=(long)(m-1)*n;
  int len=row.length;
  for(int j=0;j<len;j++){
   if(seat[j]>1)
    ret--;
   if(seat[j]<m)
    ret--;
   for(int i=0;i<len;i++)
    if((i!=j) && (row[i]==row[j]) && (seat[i]==seat[j]+1))
     ret++;
  }
  return ret;
 }
}

TopCoder SRM 469

SRM469(5/4 20:00~22:00)
スーパーボッコボコタイム．

・TheMoviesLevelOneDivOne(DIV1 Easy)
大体の解法は少し考えれば分かりました．
提出したソースがこちら．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. public class TheMoviesLevelOneDivOne {  
5.  public long find(int n, int m, int[] row, int[] seat) {  
6.   int len=seat.length;  
7.      for (int i = 0; i < len - 1; i++) {  
8.          for (int j = len - 1; j < i; j--) {  
9.              if(row[j-1]>row[j]||(row[j-1]==row[i]&&seat[j-1]>seat[j])){  
10.               int t=row[j-1];  
11.               row[j-1]=row[j];  
12.               row[j]=t;  
13.               t=seat[j-1];  
14.               seat[j-1]=seat[j];  
15.               seat[j]=t;  
16.              }  
17.              }  
18.         }  
19.         long ret=(long)(m-1)*n;  
20.         for(int j=0;j<len;){  
21.          int i;  
22.          for(i=0;j+i<len&&row[j+i]==row[j]&&seat[j+i]==seat[j]+i;i++)  
23.           ;  
24.          ret-=i+1;  
25.          if(seat[j]==1)  
26.           ret++;  
27.          if(seat[j+i-1]==m)  
28.           ret++;  
29.          j+=i;  
30.         }  
31.         return ret;  
32.           
33.  }  
34. }  
35.   
36.   
37. // Powered by FileEdit  
38. // Powered by TZTester 1.01 [25-Feb-2003]  
39. // Powered by CodeProcessor  
40.   
41.   
42. // Powered by FileEdit  
43. // Powered by TZTester 1.01 [25-Feb-2003]  
44. // Powered by CodeProcessor  

import java.util.*;
import java.lang.*;
import java.math.*;
public class TheMoviesLevelOneDivOne {
 public long find(int n, int m, int[] row, int[] seat) {
  int len=seat.length;
     for (int i = 0; i < len - 1; i++) {
         for (int j = len - 1; j < i; j--) {
             if(row[j-1]>row[j]||(row[j-1]==row[i]&&seat[j-1]>seat[j])){
              int t=row[j-1];
              row[j-1]=row[j];
              row[j]=t;
              t=seat[j-1];
              seat[j-1]=seat[j];
              seat[j]=t;
             }
             }
        }
        long ret=(long)(m-1)*n;
        for(int j=0;j<len;){
         int i;
         for(i=0;j+i<len&&row[j+i]==row[j]&&seat[j+i]==seat[j]+i;i++)
          ;
         ret-=i+1;
         if(seat[j]==1)
          ret++;
         if(seat[j+i-1]==m)
          ret++;
         j+=i;
        }
        return ret;
        
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

全体的に汚いです．そして9行目のrow[i]はrow[j]でした．焦っていたため，訂正し忘れました．
このミスによってFailed System Test．

Result:Failed System Test(0p)

・TheMoviesLevelTwoDivOne(DIV1 Normal)
＼(＾o＾)／
Result:Opend(0p)

・TheMoviesLevelThreeDivOne(DIV1 Hard)
＼(＾o＾)／
Result:Opened(0p)

・Challenges
0p

・Rating
1292->1226
次落ちたらDiv2降格は免れません．

J #1 始めたよ

Jは，APLの提案者であるケネス・アイバーソンによりAPLの後継として提案されたそうです．

処理系は↓から．
Jsoftware

↓からある程度の知識が身に付けられます．
プログラミング言語/J - プログラミングスレまとめ in VIP

こんな感じに実行されます．

   式
実行結果

例1 1~10の平均を求める

   (+/%#)1+i.10
5.5

例2 1000未満の数のうち，3か5の倍数になっているものの合計を求める

   t=.i.1000
   +/~.((0=3|t)#t),(0=5|t)#t
233168

Project Euler

problem 58
problem 67
problem 69

セルオートマトン #25 ルール23

ルール23
クラス2

時刻tでの状態	■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
時刻t+1での状態	□	□	□	■	□	■	■	■

Fig.1 rule23