2010年5月30日日曜日

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

ルール27
クラス2

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



Fig.1 rule27

2010年5月24日月曜日

Google Code Jam 2010 Round 1C

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

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

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

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しか解けないので省略.

■結果
ABC
small○(9)×(14)○(18)
large○(13)×(22)×(24)
point22018

40Point,1072位.

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

2010年5月23日日曜日

Google Code Jam 2010 Round 1B

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


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

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
ヒヨコ?クレーン?といった感じで,問題文を理解するのにかなりの時間が掛かってしまいました.分かった後はこれまた実装ゲー.

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
コーディングが間に合わず.

■結果
ABC
small○(12)○(13)×(14)
large○(14)○(17)×(30)
point26300

56Point,1257位.

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

2010年5月16日日曜日

Project Euler

problem 57
problem 81
problem 99

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

ルール25
クラス2

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



Fig.1 rule25

2010年5月15日土曜日

マージソート

何となく作りたくなったので,マージソート.

■コード
/** 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

まずは,"分割"します.

83462571

83462571

83462571

83462571

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

38462517

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

34681257

12345678

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

2010年5月14日金曜日

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=225271).
・2 q: 700
700 = Πk pkrk(pkはk番目の素数)としたとき,rkを2個並べたものを返します.10 q: 700も同様です.
・_ q: 700
上のrkを必要最低限だけ並べたものを返します.上の例でriは,2 0 2 1 0 0 0 0 …であり,2 0 2 1以降は全て0となるため,2 0 2 1となります.
・__ q: 700
rk≠0であるpkとrkを並べたテーブルを返します.

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

φ(n)は,1~nまでの自然数に対しnと互いに素なものの個数を表し,
n = Πk pkrk
としたとき(pkはk番目の素数),
φ(n) = n Πk (1 - 1/pk)
が成立します.

Euler’s totient function(オイラーのφ関数)
totient=: * -.@%@~.&.q:
totient 700
240

まず,totientを構成する動詞,副詞について説明します.
定義
x y(動詞への)引数
m n名詞
u v動詞
f g h動詞

動詞
x * yx*yTimes乗算(二項演算)
-. y1-yComplement補数(単項演算)
% y1/yReciprocal逆数(単項演算)
~. y-Nub重複要素削除(単項演算)
q: y-Prime Factors素因数分解(単項演算)

副詞
@u@v y ⇔ u v yAtop
&.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/pk)と同じ計算をしているのが分かるでしょうか?
6. y=700 に ((q:の逆演算 -. % ~. q:) y)=0.342857をかける.
240

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

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

2010年5月11日火曜日

2010年5月9日日曜日

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(t1+y, t2+y, …, tN+y)=mとします.
このとき,
m|ti+y (1≦i≦N)
であるため,
m|(ti+y)-(tj+y) (1≦i, j≦N)
よって,
m|ti-tj (1≦i, j≦N)
ここで,
gcd1≦i, j≦N(ti-tj)=n
とすれば,n=m(のはずです…).
あとは,m|t1+yとなるようにyを求めて((m-t1)%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でエラー連発でした.

■結果
ABC
small
large×
point333310

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

2010年5月4日火曜日

TopCoder 練習

TheMoviesLevelOneDivOne(SRM469 DIV1 Easy)

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)
大体の解法は少し考えれば分かりました.
提出したソースがこちら.

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降格は免れません.

2010年5月2日日曜日

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