「今週のお題：文字数で数えるローマ数字」問題解答 ( CodeIQ )

CodeIQ コードゴルフ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

簡単に言うと、ローマ数字 ( 1～3999 ) の中で、指定した文字数で表現できる数は何個あるか。文字数が標準入力から与えられる時、個数を出力するプログラムを書く問題です。

解答

golf解

以下、golf解のRuby(77)

p (1..3999).map{|i|t=0;4.times{t+=i%5<4?i%5+i/5%2:2;i/=10};t}.count(eval *$<)

golf解と言っても特別なことはしていなくて、

1～3999と範囲は決まっているので、それぞれでの文字数を求め、countメソッドによって 入力値と文字数が一致する要素の数を数えます。 文字数については、10進表記での各桁 ( 4桁分 ) に対応する文字数の合計で求めます。 千の位も含め、どの桁でも文字数は同じ規則に従いますので、1個のループとして記述することができます。

( 以上、提出版のコメント )
の通りです。

その他の解

f=->n,d{0>(m=n<d*2?n:d*4-n)?0:m<1?1: d<2?m*2:(0..4).inject(0){|s,i|s+f[n-i,d-1]*(4>>(i-2).abs)}}
n=eval *$<
p (0..3).inject(0){|s,i|s+f[n-i,3]}

ローマ数字は10進3桁と、3以下しか表現できない1桁の計4桁ですが、これを任意の桁数に対応させたバージョンです。
最上位 ( この問題では千の桁 ) が i=0～3 に対して、それぞれ f(n-i,残り桁数) 通りという計算を行い、その総和を答えとします。f 自体は再帰で求めるようにしています。
各桁は0～4文字ですが、この文字数に対応する桁は、

  • 0文字 … 0 の1通り
  • 1文字 … 1,5 の2通り ( I,V や X,L等 )
  • 2文字 … 2,4,6,9 の4通り ( II,IV,VI,IX や XX,XL,LX,XC等 )
  • 3文字 … 3,7 の2通り ( III,VII や XXX,LXX等 )
  • 4文字 … 8 の1通り ( VIII や LXXX等 )

です。なので、
f(n,d)=1\times f(n,d-1)+2\times f(n-1,d-1)+4\times f(n-2,d-1)+2\times f(n-3,d-1)+1\times f(n-4,d-1)
という漸化式が成立します。

終わりに

まああんまり変なことはしていないので、あっさりと。