2010年3月29日月曜日

TopCoder Member SRM 465

Member SRM465(3/26 10:00~12:00)

朝のSRMは初めてでしたので,起きるのが大変でした.

・TurretPlacement(DIV1 Easy)
問題を完全に読み違えており,手間取ってしまいました.寝ぼけてた所為もありますが.用事があった為,これを提出後,Log offしてしまいました.
Result:Passed System Test(130.82p)

・GreenWarfare(DIV1 Normal)
\(^o^)/
Result:Opend(0p)

・BouncingDiceGame(DIV1 Hard)
\(^o^)/
Result:Opened(0p)

・Challenges
0p

・Rating
1340->1344
とりあえず,Rating降下は抑えたといった感じです.

[ついでに]
現在Marathon Match58に参加中.

2010年3月28日日曜日

セルオートマトン #20 ルール18

ルール18
クラス4

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



Fig.1 rule18

フラクタルな感じのルールがやってでてきました.ちなみに,t=0において■を1つだけにすると,シェルピンスキーのギャスケットが出現します.

2010年3月25日木曜日

anarchy golf

8 delete blank lines
標準入力から読み取り,空行を省いて出力する.非常に安直なコードで37B.

2010年3月24日水曜日

anarchy golf

48 google
入力部分と参考演算子を改良(悪).
71B -> 67B

2010年3月23日火曜日

anarchy golf

5 Smileys Triangle
以前解いたものを更に短縮.
67B -> 63B

34 FizzBuzz
とりあえず解いてみた感じ.
84B

2010年3月22日月曜日

anarchy golf

2 echo
入力をそのまま出力せよ,というもの.とりあえず,31Bまで短縮しましたが,これ以上縮める策が現状思いつかないです.

16 even lines
偶素番目の行のみ出力せよ,という問題.40B.あと3Byteは縮めたいですが….

2010年3月21日日曜日

数学 #15 φは地球を救う

黄金比(Golden ratio)は,最も美しいとされる比
1:(1+√5)/2
です.また,(1+√5)/2を黄金数(Golden number)といい,
φ=(1+√5)/2
で表します.

今夜はφの持つ美しい性質を挙げてみましょう.

「φさんの,ちょっといいとこ見てみたいー!」
「ルート!ルート!ルート!」
「連分数が終わらない!」

φ2=φ+1

φ-1:1=1:φ=φ:φ+1

φ2=φ+1を両辺φで割ると,
φ=1+1/φ
となるので,以下の様に美しい連分数展開が成立します.


φ2=φ+1の両辺について平方根とると,
φ=√(1+φ)
となるので,以下のような美しい数式が成立します.


φ1, φ2, φ3, φ4,…と等比数列を計算すると,係数にフィボナッチ数列が出現します.
φ1=1φ+0
φ2=1φ+1
φ3=2φ+1
φ4=3φ+2
φ5=5φ+3
φ6=8φ+5
φ7=13φ+8
φ8=21φ+13


作為的ではありますが,以下も成立します.
φ=-2sin(666°)

ちなみに,出席の時の返事を「はい!」ではなく「φ!」とすると非常に美しいので一度お試しあれ.

セルオートマトン #19 ルール17

ルール17
クラス2

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



Fig.1 rule17

□□□が■になるため若干複雑な挙動を示し,左に移動する速度が1/2になっています.

2010年3月17日水曜日

TopCoder SRM 464

SRM464(3/17 0:00~0:00)

・ColorfulStrings(DIV1 Easy)
ある数に関して,部分文字列の集合を考える.それぞれの文字列の各桁を掛けたものが互いに異なる場合,その数(の文字列)をColorfulStringsという.n桁の数で辞書式順k個目のColorfulStringsを返せ,ただし,解が存在しない場合は空文字列を返す.
開始早々ひよってしまい,何故かNormal(だと気づかずに)を解いていました.
Easyに取り掛かった後は,とりあえず書いて提出.サンプルでは気付きませんでしたが,nの最大値は50なのでintでもlongでも足なくなる,ということで,再帰に書き直し.しかし,nが9以上の時にはTLEが発生.悩んだ挙句,nが9以上の時は解が存在しないことに気づき,条件分岐させ提出.
とはいえ,残念ながらまだミスが残っていました.
n=1,k=1の時の解は"0"
\(^o^)/
Result:Challenge Succeeded(0p)

・ColorfulDecoration(DIV1 Normal)
試しに書いてみましたが,O(2n)という最悪なものでしたので,明らかに実効時間が足りませんでした.ちまちま枝刈りしてみましたが無駄でした.DPでいけるかな?とも思いましたが,時間が足りず.
\(^o^)/
Result:Compiled(0p)

・ColorfulMaze(DIV1 Hard)
\(^o^)/
Result:Opened(0p)

・Challenges
一人を速攻で撃墜(TLE)しましたが,その後調子に乗って2回も撃墜ミスをしてしまいまいた.
+50 -25x2 = 0p

・Rating
1370->1340
極端には下がりませんでしたが,残念な事になっています.

2010年3月14日日曜日

セルオートマトン #18 ルール16

ルール16
クラス2

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



Fig.1 rule16

次の時刻に■となるのは■□□の時だけです.そのため■が連続しているところは消え,端っこのみが素直に右移動しています.

2010年3月11日木曜日

深さ優先探索,動的計画法,メモ化再帰

ITmediaにて,chokudai(高橋直大)さん連載の「最強最速アルゴリズマー養成講座」の最新記事が公開されました.

最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html

というわけで,格子の問題を,解説を元にサクッと組んでみました.


public class Main{
private int w, h;
private int[][] memo;

private int recursive1(int[][] grid, int x, int y){
if(y==0&&x==w-1){
return 1;
}
else if(y<0||x>=w||grid[y][x]==1){
return 0;
}
else {
return recursive1(grid, x+1, y)+recursive1(grid, x, y-1);
}
}

// 単純な深さ優先探索(DFS) O(2^(h+m))
private int count1(int[][] grid){
w=grid[0].length;
h=grid.length;
return recursive1(grid,0,h-1);
}

// 動的計画法(DP) O(h*w)
private int count2(int[][] grid){
w=grid[0].length;
h=grid.length;
int[] a=new int[w];

for(int i=0;i<w&&grid[h-1][i]==0;i++){
a[i]=1;
}

for(int j=h-2;j>=0;j--){
for(int i=1;i<w;i++){
if(grid[j][i]==1)
a[i]=0;
else
a[i]+=a[i-1];
}
}
return a[w-1];
}

private int recursive3(int[][] grid, int x, int y){
if(y==0&&x==w-1){
return 1;
}
else if(y<0||x>=w||grid[y][x]==1){
return 0;
}
else {
if(memo[y][x]!=0)
return memo[y][x];
else
return memo[y][x]=recursive3(grid, x+1, y)+recursive3(grid, x, y-1);
}
}

// メモ化再帰
private int count3(int[][] grid){
w=grid[0].length;
h=grid.length;
memo=new int[h][w];
return recursive3(grid,0,h-1);
}

public static void main(String[] args){
// 0:通過可能
// 1:通過不可能
int[][] grid=new int[][]
{
{0,0,0,0,0,0},
{0,1,0,0,0,0},
{0,0,0,0,1,0},
{0,0,1,0,0,0},
{0,0,0,0,0,0},
};
System.out.println("1:"+new Main().count1(grid));
System.out.println("2:"+new Main().count2(grid));
System.out.println("3:"+new Main().count3(grid));
}
}


深さ優先探索,動的計画法,メモ化再帰の3つです.意外なほど簡単に組めたので驚き.

「最強最速アルゴリズマー養成講座」の記事一覧は下記から.

「最強最速アルゴリズマー養成講座」最新記事一覧 - ITmedia Keywords
http://www.itmedia.co.jp/keywords/algorithmer.html

2010年3月9日火曜日

画像処理 #0 新装版のお知らせ

20回以上に渡り連載した画像処理ですが,ここら辺で新しく書き直します.
書き直す度に以前の投稿を削除しますが,御容赦を.また,連載の順番も入れ替えるので,暫くの間カオスになりますが,これもまた御容赦を.

Project Euler

problem 33

2010年3月8日月曜日

Project Euler

problem 55
problem 64
problem 65

2010年3月7日日曜日

Project Euler

problem 31
problem 32
problem 38

セルオートマトン #17 ルール15

ルール15
クラス2

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



Fig.1 rule15

全体の軌跡は右移動ですが,非常にサイケデリックな感じになっています.

2010年3月6日土曜日

TopCoder 練習

Nisoku(SRM463 DIV1 Medium)

三分探索

三分探索.二分探索じゃなくて三分探索.

二分探索は,単調関数の零点を求めるのに使われますが,
三分探索は,凸関数の極値を求めるのに使われます.

参考

実数探索三種類解説 - nodchipの日記
http://d.hatena.ne.jp/nodchip/20090303/1236058357

3分探索 - ICPC突破専用ザク
http://d.hatena.ne.jp/ir5/20090630/1246349028

fを上に凸な関数とします.
区間[a, b]を3等分して[a, c1], [c1, c2], [c2, b]の3つの区間をつくります.
この時,極大値は,上の3区間の内のどれかにあり,以下が成立します.

・極大値が[a, c1]にある(Fig.1)
⇒f(c1)>f(c2)が成立.b=c2とする.
・極大値が[c1, c2]にある(Fig.2)
⇒a=c1となってもb=c2となってもよい .
・極大値が[c2, b]にある(Fig.3)
⇒f(c1)<f(c2)が成立.a=c1とする.



Fig.1


Fig.2


Fig.3

言い換えれば,
f(c1)>f(c2)⇒極大値は[a, c2]に存在
f(c1)<f(c2)⇒極大値は[c1, b]に存在

よって,各ステップ毎に探索空間を2/3にすることが出来ます.

これを実装すると下のようになります.


double search(double left, double right, int iteration){
for(int i=0;i if(f((left*2+right)/3)>f((left+right*2)/3))
right=(left+right*2)/3;
else
left=(left*2+right)/3;
}
return (left+right)/2;
}


・例1
f(x)=x-x
df/dx=(-ln(x)-1)x-x
ですので,
df/dx=0
とおけば,
x=1/e≒0.367879441
となります.

結果:
初期値
[0, 4]
100回反復計算させた時の解
x=0.3678794519063162

・例2
鋸波
x-floor(x)
連続関数ですが,x∈Zの時は微分不可能であり極大値をとります.

結果:
初期値
[0, 4]
100回反復計算させた時の解
x=1.9999999999999996
上手く計算できたようです.

・例3
δ関数っぽいもの
δ関数は,
δ(x)=0 (x≠0)
δ(0)=∞
ですが,それっぽいものとして,

f(x)=0 (x≠0)
f(0)=1
に三分法を適用.

結果:
初期値
[-2, 2]
100回反復計算させた時の解
x=1.9999999999999996

駄目でした.連続で無いとやはり無理ですね.

Project Euler

problem 19
problem 26
problem 27

2010年3月3日水曜日

TopCoder SRM 463

約一か月振りの参戦,Div1にて.

SRM463(3/2 21:00~23:00)

・RabbitNumbering(DIV1 Easy)
N匹のウサギを番号で振り分けたい.i番目のウサギには1~maxNumber[i]までの値を振り分ける事が可能であり,どの2匹のウサギも値が重複してはいけない.(要素数Nの)配列maxNumberが与えられた時,番号の振り分け方は何通りあるか返せ,また重複させずに番号を振り分けることが出来ない場合は0を返せ.
ソート→0~N-1のループで掛算,一応重複しちゃう場合のチェックを書いて提出.
Result:Passed System Tets(240.49p)

・Nisoku(DIV1 Normal)
実数の配列が与えられる.値の範囲は[1.5, 10]である.それらを並び替えて,“+”と“×”で繋ぎ,式を作った時の最大値を求めよ,みたいな問題.
どうやるのか今一見当がつかず,[1.5, 2)は加算・乗算の組み合わせ,[2, 10]は乗算のみで提出してみたけど撃墜.
Result:Challenge Succeeded(0p)

・RabbitPuzzle(DIV1 Hard)
\(^o^)/
Result:Opened(0p)

・Challenges
撃墜しようとしたらまたまた先手を打たれました….
500は撃墜祭りでした.

・Rating
1305->1370
結果的にRatingが上昇しましたが,500を解けないようではマズイです.

次は3/17 0:00~,夜中の戦い….