「プラス・マイナス・ゼロ」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題「プラス・マイナス・ゼロ」に解答しましたので、ネタバレです。
問題
入力 n に対して、1～n の自然数に符号プラスもしくはマイナスをつけた場合に、合計が0になる符号のつけかたが何通りあるか ( $F(n)$とする ) 出力する、という問題です。
詳しくはCodeIQ Magazineの当該記事をご覧ください。
解説
結局のところ、1～n をプラス側、マイナス側の2グループに、それぞれの合計が半分ずつ同じになるような分割の仕方を調べることになります。
例えば n=7 であれば、$1+2+3+\cdots+7=28$ ですから、半分の14になる組み合わせとして、(1,2,3,5,6)や(1,2,4,7)などが挙げられますね。( 残りも自動的に半分になるため、片側だけ調べれば十分 )
※なお、$n\equiv 1,2\,\,mod\,4$ の場合はどうやっても半分に分けられないので、答えは0通りとすぐに分かります。
ということでどう考えたか、というと…。
単純に使える数の上限mを定めて、指定した合計sが作れる場合の数$f(m,s)$を漸化式で定義してあげる、というものです。具体的には次の通り。
$$ f(m,s)=\left\{ \begin{array}{ll} 0 &( m\lt 1 ) \\ f(m -1,s)+f(m -1,s-m) &( m\ge 1,\,m\lt s ) \\ f(m -1,s)+1 &( m\ge 1,\,m=s ) \\ f(m -1,s) &( m\ge 1,\,m\gt s ) \end{array}\right. \\ F(n)=f(n,\frac{n(n+1)}{4}) $$
m,sの大小関係3通りによる場合分けは、上限の数mを採用した場合に残りの合計がどうなるか、という観点によるものですね。
…片側には必ずnが入るんだから、代わりに$F(n)=2f(n-1,\frac{n(n-1)}{2})$にした方が速いじゃないか、とか、$s\gt\frac{m(m+1)}{2}$ の時点でもう0通りとして切れるよね、とかもあるのですが小さな問題なのでまあ。
で、n の場合分けも面倒なので一括で処理できるように和を4倍で考えて次のようにメモ化再帰で実装しました。Ruby(90)です。
h={}
n=eval *$<
p (g=->m,s{m<1?0:h[m+s*n]||=g[m-1,s]+((s-=m*4)>0?g[m-1,s]:1[s])})[n,n*-~n]
とても素直な実装ですね!
まあでも、こっちの方が短かったですね。Ruby(78)です。
h={}
n=eval *$<
p (g=->s,m{m<1?1[s]:h[m+s*n]||=g[s-m*4,m-=1]+g[s,m]})[n*-~n,n]
最後に
今回あんまりうまい方法が思いつかなかったのですが…。
「プラス・マイナス・ゼロ」問題のこれまでの挑戦コード眺めてて、うぉっなんじゃこりゃ、って想定外の解法に震えている（毎度）。
— Kawazoe (@riverplus) January 30, 2016
非常に気になりますね!!
他の方のコードはいつもの通り、togetterにまとめができると思います。
→ まとめができたのでリンクを載せました。
