2010年1月31日日曜日

セルオートマトン #12 ルール10

ルール10
クラス2

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



Fig.1 rule10

■,■■が左へ流れていきます.3つ以上■が続いても■■■は次のターンでX□Xになるので崩れてしまいます.

2010年1月25日月曜日

Project Euler

Problem 41
Problem 42
Problem 43
Problem 44

2010年1月24日日曜日

Project Euler

Problem 56
Problem 63
Problem 92

セルオートマトン #11 ルール9

ルール9
クラス2

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



Fig.1 rule9

最終的に周期的になりました.
いまだクラス3,4は現れず.

2010年1月20日水曜日

購入した本

ブックオフオンラインにて購入した本の一覧.

英語の構文150 Second Edition \700
基礎英文問題精講 改訂版 \450
英作文のトレーニング 入門編 \500
物理のエッセンス電磁気・熱 新課程 改訂 \450
物理のエッセンス力学・波動 新課程 改訂 \859
困ります、ファインマンさん \600
雪は天からの手紙 中谷宇吉郎エッセイ集 \400

TopCoder SRM 459

久しぶりのDiv1,Div2に戻るのは避けたかったですが・・・.

SRM459(1/20 1:00~3:00)

・Inequalities(DIV1 Easy)
不等式が複数個与えられる.不等式を最大幾つ満たことが出来るか.

簡単だったので適当に書いて提出.
Result:Passed System Test(228.38p)

・ NumberPyramids(DIV1 Normal)
ピラミッド上に数字(自然数)が並べられている.ある場所の数字は,その左下と右下の数字を足した値になっている.頂上の値と,ピラミッドの高さが与えられた時,ピラミッドは何種類作れるか.
7
4 3
2 2 1
こんなのとか,
7
2 5
1 1 4
こんなのとか.
策が見つからず,途中で寝落ち….
Result:Opened(0p)

・TheContest(DIV1 Hard)
寝落ち….
Result:Opened(0p)

・Challenges
寝落ち….

・Rating
1216->1362

ということでEasyしか解けていないのに,意外にもRating大幅上昇,過去最高Rating.いまいちRatingの基準が分かりません.

次は2/7 2:00~,真夜中の戦い…

カオス #33 Star Julia

Star Juliaとはクリスマスツリーネタで使いましたが,参考文献にあるIFSです.
説明が手抜きなのは,リンク先にある漸化式が若干謎な為です.
実際には下のようなソースで動きます.


double xa=-4*x+Math.cos(m*w);
double ya=-4*y+Math.sin(m*w);
double r=Math.sqrt(xa*xa+ya*ya);
w=Math.atan2(ya,xa);
double x1,y1;
if(mt.nextBoolean(0.5)){
x1=-Math.cos(n*w)-Math.sqrt(r)*Math.cos(w/2)/2;
y1=-Math.sin(n*w)+Math.sqrt(r)*Math.sin(w/2)/2;
}else{
x1=-Math.cos(n*w)+Math.sqrt(r)*Math.cos(w/2)/2;
y1=-Math.sin(n*w)-Math.sqrt(r)*Math.sin(w/2)/2;
}
x=x1;
y=y1;


例:
某氏より要望があった為,大きいサイズで.

m=1, n=1


Fig.1

回転させて,重ねると雪になります.


Fig.2

m=2, n=2


Fig.3

こちらは星.

折角なので壁紙サイズ.


Fig.4


Fig.5

参考文献
Paul Bourke.“Star Julia”.<http://local.wasp.uwa.edu.au/~pbourke/fractals/starjulia/>.Paul Bourke - Personal Pages.(参照2010年1月13日)

2010年1月17日日曜日

Project Euler

Problem 53
Problem 97

セルオートマトン #10 ルール8

ルール8
クラス1

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



Fig.1 rule8

全部□(=0)になってしまいました.
これは,次のターンで■となるのが,□■■だけであり,
□■■
の次のターンは次の様になります.
X■X
Xは表を見れば分かる通り,必ず□になります.というわけで次の次の時刻には□に落ち着くのでした.

2010年1月16日土曜日

今年の目標

2010年も約1/24が過ぎてしまいましたが,今年の目標.

■プログラミング関係
・TopCoderでYellowCoderになる
 現在Ratingが1216だから,あと284p必要.
・Project EulerでLevel4になる
 31問解いたので,あと119問.
・PKU Judge Online,anarchy golfへの参加
・新しい言語を一つ以上習得する

■その他
・溜まった専門書の消化
・数学,物理,英語の勉強(編入試験勉強を兼ねて)
・趣味の充実

あんまり多いと実行できないのでこの位.(でも多い)

2010年1月15日金曜日

TopCoder Member SRM 458

12/18以降,2回連続不参加でしたので約1カ月ぶりの参加.

Member SRM458(1/15 1:00~3:00)

・Desertification(DIV2 Easy)
セルで構成された「島」が与えられる.セルは,forest(=森)か desert(=砂漠)のどちらかの状態を持つ.また,単位時間が経過すると,砂漠は自セルの上下左右の4近傍にある森を砂漠に変える.初期状態の島から時間Tが経過した時,砂漠となっているセルはいくつあるか.

■□□□
□□□□
□□□■
□□□□

■■□□
■□□■
□□■■
□□□■

■■■■
■■■■
■■■■
□□■■
こんな感じ(□=森,■=砂漠).■は14個.

Tの最大値は10億でしたので,単純ループでは2秒以内に終わらないです.島の初期状態が全て森の時は0を返し(いくら時間が経過してもずっと森のまま),ループ中に島が全て砂漠化した時には終了条件を待たずして終了するようにして提出.

Result:Passed System Test(220.00p)

・BouncingBalls(DIV2 Medium)
ライン上にボールが並んでいる.それぞれのボールは等確率で左or右に動来始める(=単位時間で+1or-1移動する).ボール同士が衝突した時は,弾性衝突をするものとする.全ボールの初期位置が与えられた時,T時間以内でボール同士が衝突する回数の期待値を求めよ.

一々ボールを動かして云々とかやると,2秒以内に終わるはずが無いので,ボール同士の距離の差でどうにか計算しました.ボールがN個あった場合,ボールの動き方は2N通りありますが,Nの最大値は12でしたので再帰を使用しても大丈夫でした.

Result:Passed System Test(260.44p)

・ProductTriplet(DIV2 Hard)
minx ≦ x ≦ maxx
miny ≦ y ≦ maxy
minz ≦ z ≦ maxz
x * y = z
となる(x, y, z)の組みは幾つあるか.

6つのパラメータは範囲が[1, 1000000000]なので,困りました.時間もMediumで取られてしまって,手をつけられず.

Result:Opened(0p)

・Challenges
あからさまなミスを撃墜しようとしたら,他の方に先に撃墜されました….

Rating
1155->1216

というわけで,BlueCoderに昇進.再びDiv1の世界へ….

Project Euler

Problem 45

2010年1月14日木曜日

TopCoder 練習

1/14
TheSquareDivTwo(SRM457 DIV2 Easy)
TheTriangleBothDivs(SRM457 DIV2 Medium)

2010年1月13日水曜日

カオス #32 Clifford Attractor

再々びClifford Attractor.そのうちまたいつかもしかしたらいつぞやに作ります.


Fig.1 a=1.1, b=-1.1, c=1.0, d=1.4


Fig.2 a=0.7, b=-1.8, c=1.6, d=0.9


Fig.3 a=0.7, b=-2.0, c=1.6, d=0.9

2010年1月10日日曜日

セルオートマトン #9 ルール7

ルール7
クラス2

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



Fig.1 rule7

…□□■□□…
…■■■□■…
…□□□□□…
となり為,孤立しているところは消えてしまいます.
これも最終的に周期的なものに落ち着きます.

2010年1月7日木曜日

カオス #31 Langton's ant

「Langtonのアリ」です.
Christopher Langtonが考案しました.概要は以下.

格子状の平面を構成する.各マスは黒(=0)に初期化.ある1つのマスにアリを配置.アリは各ステップで上下左右いずれかのマスに移動できる.アリの移動規則は以下に従う.

・黒いマスにアリがいた場合
90°右に方向転換,そのマスの色を反転させ,1マス前進.
・白いマスにアリがいた場合
90°左に方向転換,そのマスの色を反転させ,1マス前進.

この規則でアリはかなりカオスな挙動を示します.
しかし,10000程歩いた後,真っ直ぐな(斜め方向の)「道(highway)」を作り始めます.この道は,LangtonのアリのAttractorかもね,らしいです.

Case 1:
格子:1024x1024
アリの数:1
初期条件:
位置:(512, 512)
方向:上


Fig.1 step=0
白い点がアリです.


Fig.2 step=1000
小さい範囲でゴニョゴニョと.赤いマスは黒を反転させたということです.


Fig.3 step=5000
範囲が大きくなりましたが,直進する気配がありません.


Fig.4 step=10000
10000step経ちました.


Fig.5 step=10500
こんな,


Fig.6 step=11000
感じで,


Fig.7 step=11500
のんびりと,


Fig.8 step=12000
のびていきます.


Fig.9 step=500000
長時間経過後.

Case 2:
格子:512x512
アリの数:3
初期条件:
位置:(128, 128), (256, 256), (384, 384)
方向:上, 上, 上


Fig.10 step=0
3アリ配置したナリ.


Fig.11 step=10000
ここまでは一緒.どのアリが反転したかによって色を変えたナリヨ.


Fig.12 step=50000
カオス.


Fig.13 step=500000
サイケ.

参考文献

Wikipediaの執筆者たち.“ラングトンのアリ”.<http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%82%B0%E3%83%88%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AA>.Wikipedia.(参照2009年12月23日)

2010年1月3日日曜日

セルオートマトン #8 ルール6

ルール6
クラス2

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



Fig.1 rule6

連続しているところは一部消えてしまい,最終的には左に流れていく感じで周期的になります.