「キャンディ・アンド・チョコレート」問題解答 ( CodeIQ )
CodeIQというところでプログラミング問題「キャンディ・アンド・チョコレート」に解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 空白区切りで入力される自然数 $n,k\,(1\le k n\le 100)$ に対し、$F(n,k)+G(n,k)$の値を出力する
- $F(n,k)$とは $n$個のキャンディを幾つかのグループ ( 1グループも可 ) に分割するとき、その最大グループのキャンディの個数が丁度 $k$個になる分割が何通りかを表す数である。
- $G(n,k)$とは $n$個のチョコレートを$k$グループに分割する方法が何通りかを表す数である。
- いずれも、個々のキャンディやチョコレートは区別しない。
キャンディの場合、例えば次の図のような分割が挙げられますので、$F(8,3)=5$です。
また、チョコレートの場合、例えば次の図のような分割が挙げられますので、$F(9,4)=6$です。
解説
規則性の整理
まずはお約束として漸化式を考えてみます。
キャンディの場合、最大グループの$k$個を除けば、高々$k$個が最大になります。そのため、以下のように$F(n,k)$を定義することができます。
- $F(n,k)=0\,\,( n\lt k )$
- $F(n,1)=F(n,n)=1$
- $F(n,k)=\sum_{j=1}^k F(n-k,j)$
続いてチョコレートの場合です。こちらは最小グループの個数をベースに考えます。
この図は20個を、最小3個の5グループに分ける場合を表すものですが、底の部分の11個を確保すれば、残り9個を4グループに分けるのと同じことです。
そのため、
- $G(n,k)=0\,\,( n\lt k )$
- $G(n,1)=G(n,n)=1$
- $G(n,k)=\sum_{j=1}^{\lfloor n/k\rfloor} G(n-k(j-1)-1,k-1)$
と定義できます。
正直、これで実装するには十分なのですが…。実はこの問題には謎が隠されていたのです。
謎の解明
実は、$F(n,k),\,G(n,k)$の値を色々計算してみると、奇妙なことに値が悉く一致するのです。まあだとすると一方だけ計算すればいいので楽なのですがこれは偶然でしょうか?
…とまあ、ここまで言うからには$F(n,k)=G(n,k)$なのですが。何故かというと、$F(n,k)$の数え方は、$G(n,k)$の数え方の視点を変えたものに過ぎないからです。
次の図のように、端を揃えて、上の段の方が個数が少なくなるように、各段は全て横一列につなげてモノを積むことを考えます。
この場合は、10個を3段です。これは明らかに$G(10,3)$を考える時のグループ分けに対応しています。
ここで、これを縦に分割してみます。
そうすると、端から順に個数が整列されていて、しかも最大グループ内の個数は段数と同じ3です。ということは、これは$F(10,3)$を考える時のグループ分けに他なりません。
ということで、キャンディ・チョコレート、両者の分割の方法は1対1に対応することが分かります。そのため、$F(n,k)=G(n,k)$なのです。
実装
では実装ですが、どちらかというと楽なのは$F(n,k)$の方なので、そちらを求めて2倍することを考えます。その際、上であげた漸化式をそのまま実装しても良いのですが、もうちょっと整理してみます。
- $F(n,k)=\sum_{j=1}^k F(n-k,j)$
ここから次も分かります。
- $F(n-1,k-1)=\sum_{j=1}^{k-1} F(n-k,j)$
そのため、辺々差し引いて、Σのない形に落とし込むことができます。
- $F(n,k)=F(n-1,k-1)+F(n-k,k)$
もう一つ工夫して、次のような$H(n,k)$を用意します。
- $H(x,y)=H(x,y-1)+H(x-y,y)$
- $F(n,k)=H(n-k,k)$
こうするともはや再帰で計算せずとも、添え字 0～x の配列を y回、幾つか前の要素を足しつつ更新していけば、目的の値が得られることになります。 ということで提出したのが、次のRuby(85)です。
後で値を2倍する代わりに、初期の配列 ( $H(n,1)=1$相当 ) を用意する時に値を倍しておきます。
形としても分かり易いですし、恐らく実装としても一番短くなるのではないかと思います。
終わりに
実は出題者の方のtwitterを見なかったら謎があるなんて考えなかった…というのは秘密です。いやでも調べるつもりだったし!
