2016-03-09

CodeIQ 挑戦の記録 : 第83回「超」整理法に従って並べなおして！

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると下記の通り

標準入力より本の冊数nが与えられる。
n冊の全ての並び方について元の並び方に戻す事を考える。
並び替え方は任意の本を左端に挿入し、それ以外を順に右にずらす。これの繰り返し。
最短の回数で全パターンの並び替え回数の合計を出力する。

方針

f(n)を全パターンの回数の合計とすると漸化式は次の通り

${f(1)=0}$
${f(n)=n!-1+n \times f(n-1) }$

提出したコードは下記の通り。Ruby(76)

def c(n);return 0 if n==1;(1..n).inject(1,:*)-1+n*c(n-1);end;p c(gets.to_i)

どこからこの漸化式が出てきたかですが、例によって?
勘です。

というか、出題者である増井先生の著書「プログラマ脳を鍛える　数学パズル」にほとんど同じ過去問が記載されています。
その問題では、自動採点では無く1秒の時間制限が無いのと、入力のnが7で、本問の最大15よりかなり小さい数ですので、模範解答も全探索と少し工夫して高速化したものを挙げられてました。
そして、参考程度に以下の様に書かれてありますので引用させて頂きます。

数学的に対称群で考えると、巡回置換の積で求められますので、以下の漸化式で表すことができます。

この後に漸化式が記載されているのですが、大学で数学をやっていない文系趣味グラマーとしては群論はさっぱりですので、この過去問でどうしてその漸化式になるか全く分かりません。
そこで、下記に記載する全探索のコードを書いて、ある程度小さい数値で試した結果から漸化式を予想するという乱暴な方法で上記の式を導いたという次第です。

全探索のコード（但しnの最大は9まで）

言語:c++
幅優先探索を使用して、ある並び方から問題文の逆の並べ方で生成する全てのパターンについてその回数を加算した合計を出力するもの。
実行時間は「実行くん」でn=9のケースで約0.5秒　　

では、

Sponsored Link

2016-03-02

CodeIQ 挑戦の記録 : 第82回「今週のアルゴリズム：どの会場でも均等にセミナーを参加して！」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると下記の通り

あるセッションのタイムテーブルの参加パターンを考える
同時間帯にm個の会場でセッションが行われ、nコマあるとする
どの会場へも同じ回数で参加するとすると、参加パターンは何パターンあるか解答する。
全く参加しないパターンも含む
${ m \le 6 , n \le 10 }$

方針

組み合わせの問題として考える。
それぞれの会場で参加するセッションの回数は同じにする必要があるので、それぞれの会場で参加する回数をp回とするとpの取りうる範囲は $ 0 \le p \le floor(n \div m) $

会場1から会場mのそれぞれについて、

会場1では$n $回のセッションの中から$p $回を選ぶ事ができる。
会場2では$n $回から会場1で選んだ$ p$回を除いた$ (n-p) $回から$p $回を選ぶ。
同様に会場3では$(n-2p)回からp $回を選ぶ・・・

これを全ての会場分について掛けたものが一つの会場で$p $回参加する場合のパターン数となる。
つまり、組み合わせ$ _nC_k $ を用いて、

${ _nC_p \times _{(n-p)}C_p \times _{(n-2p)}C_p...}$

これをpについて1から$ floor(n \div m) $まで計算したものを加算し、全く参加しない1パターンを加えて解答とする。

実装

提出したコードか下記の通り(Ruby)

Sponsored Link

2016-02-24

CodeIQ 挑戦の記録 : 第81回「今週のアルゴリズム：長方形から作る正方形」

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると、

標準入力から整数m,nが与えられる。
長辺がmの長方形から(短辺の長さx短辺の長さの）正方形を切り取り、残った長方形から更に正方形を切り取るという事を長方形が無くなるまで繰り返す。
この時、できた正方形の数を数えるが、長辺がm以下の長方形で正方形がn個できるものの縦・横のパターンが何通りあるか解答する。
$ m \le 1000 $

方針

動的計画法を用いる。
${i \times j}$ $(i<j)$ の大きさの長方形から切り取る事ができる正方形の個数を ${f(i,j)}$ とすると、漸化式は下記の通り

${ f(1,j)=j }$
${ f(i,j)= floor( j \div i ) + f(( j \% i ), i) }$ $ (i<j) $

漸化式の説明

${1\times j}$ の大きさの長方形には $1\times 1$ の大きさの正方形が ${j}$ 個含まれる。
${i\times j}$ の大きさの長方形$(i<j)$には ${i\times i}$ の大きさの正方形が ${j\div i}$ 個と、これらの正方形を取り除いた ${i\times (j \% i)}$ の長方形が残るが、これは縦・横を入れ替えた大きさのものを計算済みであるのでその結果を利用する。

f:id:ibeckuu:20160223223623j:plain
(1,j)
${1 \times 1}$ の大きさの正方形が ${j}$ 個

f:id:ibeckuu:20160223223801j:plain
(2,j)
${2 \times 2}$ の大きさの正方形が ${j\div 2}$ 個
$+$ $ 2 \times (j \% 2)$の大きさの長方形（＝正方形の個数は既に$(j \% 2,2)$に代入されているのでこれを参照する）

f:id:ibeckuu:20160223231056j:plain
(3,j)
${3 \times 3}$ の大きさの正方形が ${j\div 3}$ 個
$+$ $ 3 \times (j \% 3)$の大きさの長方形（＝正方形の個数は既に$(j \%3,3)$に代入されているのでこれを参照する）

f:id:ibeckuu:20160224005645j:plain
(4,j)
${4 \times 4}$ の大きさの正方形が$j \div 4$個
$+$ $4 \times (j \% 4)$の大きさの長方形（＝正方形の個数は既に$(j \%4,4)$に代入されているのでこれを参照する）

以上を利用して実装したのが下記(Ruby)

Sponsored Link

2016-02-19

CodeIQ 挑戦の記録 : 「プラス・マイナス・ゼロ」問題

CodeIQというサイトで問題に挑戦した記録です。

「プラス・マイナス・ゼロ」問題

問題文を要約すると、
自然数1からnまでを並べ、それぞれの前に「＋」か「ー」を配置した式を考える時、
合計が0になる「＋」と「ー」の並べ方が何通りあるか解答するもの。

方針

仮にa+b-c-d=0が成り立つとする
これを変形しa+b=c+dとする。
この場合、題意よりaからdは1から4までの数値であり、 aからdまでを全て加算した値は1から4までの公差1の等差数列の和に等しい。
ゆえに、この場合、a+bとc+dは1から4までの等差数列の和を2で割ったものに等しい。
これより、1からnまでの整数の中で、等差数列の和を2で割った値に等しくなる組み合わせの数を解答とする。

なお、等差数列の和の公式 ${ n(1+n)/2 }$ において、この和の更に1/2と等しくなる組み合わせを求めるので、
${ n(1+n) }$ が4で割り切れなければ題意を満たす自然数の組はない。
(nを4で割って余りが1か2であれば問題の等式はできないので0を解答とする）

実装

1からnまでの自然数の中で ${ n(1+n)/4 }$ と等しくなる組み合わせを探す事になるが、幾つかの要素を組み合わせて最適なものを選んだパターン数を求めるという事では有名問題:ナップサック問題の変形と考えて良い。
*ナップサック問題の説明（動的計画法スライド・4ページから）

プログラミングコンテストでの動的計画法 from Takuya Akiba

www.slideshare.net

動的計画法を用いる

1からiまでの数値の中で加算してjになる組み合わせのパターン数を ${ f(i,j) }$ とすると、　　

下記の通りの漸化式で表す事ができる。

${ f(0,0) = 1 }$
${ f(i,j) = f(i-1,j) + f(i-1,j-i) }$

下記の様にdpテーブルを作成し、縦軸(i)をnまでの数値、横軸(j)を加算した数値、テーブルの要素はパターン数とすると、
i番目の数値jはi-1番目の数値j-iにiを加えたものとi-1番目の数値をそのまま持ってきた2パターンの合計である。

f:id:ibeckuu:20160219001254j:plain

以上を用いて実装し、提出したソースコードは下記(Ruby)

また、最初は下記のメモ化再帰で実装したが、ローカルで試した時に最大の入力値(48)で1秒の時間制限に間に合わなかった為、上記の動的計画法版で提出した。
（上記のものは余裕でクリアできた）　　

Sponsored Link

2016-02-19

CodeIQ 挑戦の記録 : バイバイマンを数えよう

CodeIQというサイトで問題に挑戦した記録です。

バイバイマンを数えよう

問題文を要約すると、
「バイバイマン」は1日目の大きさが1で、2日目が2、3日目が4と、毎日2倍になる。
但し、10を超えると分裂し、16なら1と6に分裂し同様にバイバイを繰り返す。
100日目までのバイバイマンの数を列挙する。

提出したコード (Ruby 45byte)

a=[1]*4;b=0;100.times{c=a[-4];a<<c*2+b;p b=c}

方針

漸化式は下記の通りになります。

${ f(0)=0 }$
${ f(1)=f(2)=f(3)=f(4)=1 }$
${ f(n) = 2*f(n-4) + f(n-5) }$

これを元に実装して正解しているのでこの漸化式も正しいのでしょう。
しかし、なぜこれが正しいか、自分には説明できません。
どうやって導いたかと言えば、紙と鉛筆でシミュレートし、数値の変化に合いそうな式を勘で当てはめていったという・・・

Rubyの最短まで後8文字で、この8文字はとてつもなく遠いですが、自分としてはまずまずの出来かなと思ってます。
大変楽しめました。
ありがとうございました。> @ozy4dm 様、参加者のみなさん

Sponsored Link

2016-02-18

CodeIQ 挑戦の記録 : 第80回「今週のアルゴリズム：回数指定のじゃんけん」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

第80回「今週のアルゴリズム：回数指定のじゃんけん」

問題文を要約すると以下の通り

標準入力よりAさん、Bさんそれぞれの持っているコインの枚数、上限の回数が与えられる。
Aさん、Bさんがじゃんけんをして、勝った方が負けた方からコインを1枚受け取る
いずれかのコインがなくなるか、上限に達するまでじゃんけんを繰り返した時、いずれかのコインが無くなるパターンが何通りかを解答する。

方針

(1)メモ化再帰によりじゃんけんでコインの枚数が変化するパターンをシミュレートする

題意の通り、じゃんけんで <Aが勝つ> <Bが勝つ> <あいこ> それぞれを試したものが最初に提出したコード。
何も考えず引数を3つ取った再帰で実装したが、少し考えれば2人のどちらが勝つかは、1人のコインの増減にまとめられるので引数は2つにできた。
メモ化は3重のハッシュを用いており、この程度の大きさの入力であれば問題無かったが、安直なコードだと思う。

(2)動的計画法によりシミュレートする

動的計画法を用いて再提出したもの

二次元配列dpを用意する（縦軸はじゃんけんの回数0からn、横軸はAのコインの枚数。Bは総数から引けば分かるので無視。0からA+Bの総数）
初期値としてAのコインの枚数を示す要素dp[0][枚数]に1を代入。
二重ループにて順に（負け）dp[i+1][枚数-1]、（あいこ）dp[i+1][枚数]、（勝ち）dp[i+1][枚数+1]　それぞれに　dp[i][枚数]の要素を代入する。
コインの枚数が0またはA+Bの総数に達した場合は、別の変数に代入しておき、最終的にこの変数の値を解答とする。

コードは以下の通り

実行速度はほとんど変わらなかった。
なお、この問題は簡単なシミュレーションであるが、同じアルゴリズムで株取引（信用取引）などをシミュレートして期待値を計算できると思ったので計算してみた。
よければこの記事も御覧ください。

t.co

2016-02-18

100万円を元手にFXを3ヶ月運用してみて200万円になる確率と20万円になる確率をプログラムを組んで計算してみた

100万円を元手にFXを3ヶ月運用してみて200万円になる確率と20万円になる確率をプログラムを組んで計算してみた・・・驚きの結果が、と言いたかったがまあ、普通だった

計算結果

3ヶ月（60回約定とした）後の金額	確率
20万円以上 30万円未満	0.006795％
30万円以上 40万円未満	0.308008％
40万円以上 50万円未満	2.312749％
50万円以上 60万円未満	5.220715％
60万円以上 70万円未満	10.698449％
70万円以上 80万円未満	7.729905％
80万円以上 90万円未満	19.162910％
90万円以上 100万円未満	10.387716％
100万円以上 110万円未満	10.052491％
110万円以上 120万円未満	16.837724％
120万円以上 130万円未満	6.133299％
130万円以上 140万円未満	0.000000％
140万円以上 150万円未満	4.546171％
150万円以上 160万円未満	3.131831％
160万円以上 170万円未満	1.971992％
170万円以上 180万円未満	1.063034％
180万円以上 190万円未満	0.000000％
190万円以上 200万円未満	0.332902％
200万円以上になって抜ける	0.103306％
20万円以下で強制退場になる	0.000004％
初期資金より減る	55.827250％
初期資金以上になる	44.172750％

（上記計算時のパラメータ）

1回に投資する金額・・・手持ち資金の10%
レバレッジ・・・20倍
為替相場の変動割合・・・2%（1ドル100円で円売りドル買いをしたものが1ドル102円になった等）
スプレッド・・・1銭

として、3ヶ月で60回の利益確定か損切りのいずれかを繰り返したとした場合

確率の求め方

現在の手持ち資金に対して、下記の計算方法で利益を確定した場合と損切りを行った場合の2通りの手持ち資金の変化をシミュレートしていき、幾らになったかを全ての場合の数で割って確率を求める

（利益を確定する）　手持ち資金　＋（手持ち資金 X １回に投資する割合 X レバレッジ X （為替変動の割合 % ースプレッド（銭単位））
（損切りをする）　手持ち資金ー　（手持ち資金 X １回に投資する割合 X レバレッジ X （為替変動の割合 % ＋スプレッド（銭単位））

上記2通りの手持ち資金の変化を60回繰り返すシミュレーションを行う。
（シミュレーションの例）

f:id:ibeckuu:20160218001750j:plain

この例では3回で8通りの結果になる。（2の3乗=8）
　上図では3回目の青枠で括った金額（4通り）が元手の100万円以上になっており、赤枠で括った金額（4通り）が100万円を下回る結果となっている。

この例では、3回投資を行った結果が、100万円以上になる確率50%（全8通り中4通り）、100万円未満になる確率も50%（全8通り中4通り）になる、と計算する事ができる。

これを60回繰り返し、それぞれの金額が出現する場合の数を全体の場合の数で割り、確率を求める。　　

（最大で2の60乗=約115京2921億通りになる）

プログラム

計算をしたソースコードは以下の通り (Java)
Javaができる方は標準入力からのパラメータを変えていろいろ実行してみて下さい。

パラメータは標準入力よりカンマ区切りで、
手持ち資金に対する１回の投資割合　％, レバレッジ　倍,　スプレッド　銭（0.01%）,　為替相場の変動割合　％（全て整数値）