マヨイドーロ問題 のソースコードを載せてもいいらしいので載せる

https://twitter.com/hyuki/status/675266662073942016

投稿してもOKだそうです。


他のソースコードと異なる(っているであろう)点を挙げるならば、「汎用的な再帰関数の高速化」をやろうとした、でしょうか。要は頭使ってない。
タイムアタックなんてやるんじゃなかった。
もちろん、この記事の後半に関数の簡単化と再帰の除去を載せましたよ!

rubyは始めて間もないので、幼稚な記述が多め。

12:08 追記:
リンク貼ってなかった。マヨイドーロとは?http://www.hyuki.com/codeiq/#c19


2016/03/23 修正
説明文を大幅に書き換えました。
ソースコードはあえて書き換え無し。
動的計画法等の用語を導入したり。mathjax使ったり。


もくじ

・基礎となるアイデア。
  素朴すぎる考え

・そうは簡単に通らないマヨネロード
  気合で高速化して全問正解

・もっと楽にできる?
  素朴すぎる考えを整形

・再帰を使わない形に変形できるか?
  教科書を読みながら、再帰を取り除きます。




--------------------------------
基礎となるアイデア。読み飛ばしてください。

単純なプログラムは以下のようになります。説明なし。

def funcP(n,pos,v)
if (n<0) # これ以上反転できないのに反転した=ノーカウント
return 0
end
if (pos < 0) # Yの出口に出た=数える
return 1
elsif (2 < pos) # Zの出口に出た=ノーカウント
return 0
end
# 反転した分身と反転しなかった分身が数えに行く
return funcP(n,pos+v,v)+funcP(n-1,pos-v,-v)
end

p funcP(gets.to_i,1,1)



--------------------------------
そうは簡単に通らないマヨイロード

実際にテストに投げてみると、「N=2015」というhorribleな値をよこしてきます。
結論から言えば、N=2015という入力は凄い桁数の解になります。
ここではRubyなので、整数表現を気にすることは止めます。

高速化としてまず挙げられるのは、動的計画法(以下DP)です。
まずは、メモ化を使ったDPを実装してみます。

#再提出1
$tmpfunc = {}

def funcP(n,pos,v)
if (n<0)
return 0
end
if (pos < 0)
return 1
elsif (2 < pos)
return 0
end
#計算したことがあるなら、その解をそのまま返す
if ($tmpfunc[[n,pos,v]] != nil)
return $tmpfunc[[n,pos,v]];
end
r = funcP(n,pos+v,v)+funcP(n-1,pos-v,-v)
#暗記する
$tmpfunc[[n,pos,v]]=r
return r
end

while cin = gets
p funcP(cin.to_i,1,1)
end


このコードで全部通ります。




--------------------------------
もっと楽にできる?

上の関数は、パラメータが3つもあるので、なんとか減らしたい所。

1つに減らそうと考えましたが、方向の情報が排除できなかったので、今はあきらめます。
アリスさんの位置をBに固定します。Zに到着したアリスさんはノーカウント。

Z向きのとき。
・Bで反転し、Aを直進し、「Yに到着」
・Bで反転し、さらにAで反転し、「Z向きでBへ到着」
・Cで反転し、「Y向きでBに到着」
Y向きのとき。
・Bで反転し、さらにCで反転し、「Y向きでBへ到着」
・Aを直進し、「Yに到着」
・Aで反転し、「Z向きでBに到着」

すると、割と綺麗なコードが出てきます。

def funcPZ(n)
if (n<1)
return 0
end
if (n==1)
return 2
end
return funcPZ(n-2)+funcPY(n-1)+1
end

def funcPY(n)
if (n<2)
return 1
end
return funcPZ(n-1)+funcPY(n-2)+1
end

while cin = gets
p funcPZ(cin.to_i)
end

連立方程式を立てて、弄り倒してみます。

%$funcPZ(n) = funcPZ(n-2) + funcPY(n-1) + 1$%
%$funcPY(n) = funcPZ(n-1) + funcPY(n-2) + 1$%

nを引いたり式を引いたりすると、次の式が得られます。

%$funcPY(n) = 2 * funcPZ(n-1) - funcPZ(n-3)$%

つまり、%$funcPY$%は%$funcPZ$%だけで表現できる・・・。

ということは、%$funcPZ$%に代入すれば・・・

%$funcPZ(n) = 3 funcPZ(n-2) - funcPZ(n-4) + 1$%
%$funcPZ(3)=7$%
%$funcPZ(2)=2$%
%$funcPZ(1)=2$%
%$funcPZ(0)=0$%

%$funcPZ$%だけになりました。パラメータ1つで表現できるように。
def funcPZ(n)
if n==3
7
elsif n==2
2
elsif n==1
2
elsif n<=0
0
else
3 * funcPZ(n-2) - funcPZ(n-4) + 1
end
end

while cin = gets
p funcPZ(cin.to_i)
end


よく見ると、[0][1 2][3 4][5 6]...の解が同じになっている、奇数nから偶数n、偶数nから奇数nの引数関数が出てこないのを見て、

def funcPZ(n)
if n==1
2
elsif n<=0
0
else
3 * funcPZ(n-1) - funcPZ(n-2) + 1
end
end

while cin = gets
p funcPZ((cin.to_i + 1) /2)
end

見やすくなりました。スッキリ。




----------------------
再帰を使わない形に変形できるか?

ところで、「再帰を使った関数を再帰を使わずに表現する」(プログラミングの話ではなく、数学の解析学の話)を
聞いたことがありませんか?

教科書探ったらありました。
「2階定係数の線形差分方程式」うんたらかんたら。

やってみよう。

次の式が既に得られています。

%$f_{n+2} - 3 f_{n+1} + f_{n} = 1$%

はじめに、次の条件を満たすFを求めます。

%$f_{n+2} = f_{n+1} = f_{n} = F$%

%$F=-1$%が得られるのがわかります。(略)


%$F$%を使って、式を変形させます。

%$(f(_{n+2} -F) - 3 (f_{n+1}-F) + (f_{n} -F) = 0$%

ここで、%$g_n = f_n - F$%を定義します。
さらに、%$h_{n+1} = g_{n}$%も定義します。

すると、次のように書き表せます。

%$g_{n+2} - 3 g_{n+1} + h_{n+1} = 0$%

変形して、

%$g_{n+1} = 3 g_n - h_n$%


そして、次のような連立方程式を考えます。2つの式は上から引っ張ってきたものです。

%$g_{n+1} = 3 g_n - h_n$%
%$h_{n+1} = g_n$%

行列にします。行列%$G_n$%を定義します。

%$G_n=\left(\begin{array}{ccc} g_{n+1} \\ h_{n+1} \\ \end{array} \right)=\left(\begin{array}{ccc} 3 & -1 \\ 1 & 0 \\ \end{array} \right) \left(\begin{array}{ccc} g_{n} \\ h_{n} \\ \end{array} \right)$%

定数部分の行列は%$A$%と表現することにします。

%$G_{n+1}=AG_n$%

%$G_{n+1}=AG_n$%は、次のように変形できます。

%$G_n = AG_{n-1} \\
= A(AG_{n-2}) \\
= AAG_{n-2} \\
= AAAG_{n-3} \\
= AAAAG_{n-4} \\
= (A^{n-1})G_1$%

ところで、%$G_n$%は%$( g_n h_n )^T$%でした。

%$g_1 = f_1 - F = 2 - (-1) = 3$%
%$h_1 = f_0 - F = 0 - (-1) = 1$%

%$g_{n+1} = f_{n+1} - F$%
%$h_{n+1} = f_n - F$%

以上まとめると、こんな式が得られます。

%$G_n=\left(\begin{array}{ccc} f_{n+1} \\ f_{n} \\ \end{array} \right)=\left(\begin{array}{ccc} 3 & -1 \\ 1 & 0 \\ \end{array} \right)^n \left(\begin{array}{ccc} 3 \\ 1 \\ \end{array} \right)$%

再帰しなくても%$f_n$%が求まる!

行列の階乗と聞くと思わず「対角化!固有値!固有ベクトル!」と叫びたくなる学生も多いと思います。
この行列の固有値求めるとルートが出てきます。求めました。

しかしnは整数ですし、計算量はlog2015程度なので、行列が扱える言語ならば大抵は1秒切れます。

これらを実装します。
#再提出2
require 'matrix'

def calc(n)
@A = Matrix[[3,-1],[1,0]]
@A=(@A**n)* Matrix[[3],[1]]
return @A[1,0]-1
end

while cin = gets
p calc((cin.to_i + 1) /2)
end


おわり。

ちなみにコレ、フィボナッチ数列です。終わってから気づきました。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : codeIQ ruby

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1467位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
265位
アクセスランキングを見る>>