読者です 読者をやめる 読者になる 読者になる

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ページから)

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