「今週のお題：一列に並べたマトリョーシカ」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力nに対し、サイズが1～nのマトリョーシカから任意個選ぶ。それら全ての選び方の中で、選んだマトリョーシカを一番外側に配置して、それ以外の全てのマトリョーシカをいずれかの入れ子にするような配置の方法が何通りあるか、その最大値を出力する。
蛇足ながら、マトリョーシカというのは、サイズ順に入れ子にできる人形の一種です。
例えばn=4の時は、4,3のマトリョーシカを ( 外側に配置するように ) 選んだとき、下の図のように残り2,1のマトリョーシカについては4通りの配置があり、これが全ての選び方の中での最大の配置の数になります。
解説
今回提出したのは、次のRuby(41)です。…まあ、~-nの~-はなくてもいいはずなので、2文字無駄ということになりますが。
p (1..~-n=gets.to_i).map{|k|k**(n-k)}.max
さて、今回の問題は、あくまで最大のケースを見つけるのが主眼なので、一番外側のマトリョーシカは、大きい順に決めてしまって構いません。 つまり、例えばn=4であれば、外側のマトリョーシカを4,2とするような配置を考える必要はなくて、2個選ぶなら4,3にするとか、3個選ぶなら4,3,2にするといった具合になります。
そうすると、残りのマトリョーシカについては、大きい順にどのマトリョーシカに入れるか、重複順列を考えることで入れ方を数えることができます。 そのため、一番外側のマトリョーシカを k 個とした場合、パターン数は $k^{n-k}$ です。各 k に対するパターン数を調べ、その中から最大値を選べばそれが答えとなります。
終わりに
気付いてしまえば計算自体は簡単でしたね。…しかし、問題を解きっぱなしで提出したものだとばかり勘違いしていて、結局締め切りギリギリになってしまいました。( 気付いて良かった )
それで提出順が狂って、間違えて次の問題の記事を締め切りが来る前に公開したような気がするけど、そんなことはなかったことにしたぜ!! …はあ。
