PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 89 / ローマ数字

ローマ数字の記法は一つの数について沢山ある場合が存在する。しかし,ある数については最良の記法が必ず存在する。

例として16は次のように表せる。

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

最後の例は最小の文字数で表せるという意味で最も効率がよい。

11Kのテキストファイル fileroman.txt は1000個のローマ記法で書かれた数を含んでいる。これらは正しい記法に従っている。つまり,大きい数から順に書かれていて,引き算ペアのルールにも従っている。ただし,最小の文字数で表されているとは限らない。

最小形で書いたときに, 何文字節約できるかを求めよ。

注:ファイル中の全てのローマ数字に5つ以上の同じ文字が連続して含まれることはない。


FAQ: ローマ数字のルール

IVXLCDM
1510501005001000

■基本法則1

すべての文字はサイズの降順に並ぶ。

■基本法則2

引き算ペアについて。

X (10) + IX (9) として19=XIXと表せる。ただし,8をIIXのように二文字以上を引くことは許されない。

  • I, X, Cのみが引き算ペアの最初の文字として許される
  • IはVまたはXの前に来ることが許される
  • XはLまたはCの前に来ることが許される
  • CはDまたはMの前に来ることが許される

Problem 89 - Project Euler


Mathematica に変換用の関数をもっていました。

  • FromRomanNumeral はローマ数字→10進法の整数
  • RomanNumeral は10進法の整数→ローマ数字

一旦10進法に直したものをもう一度ローマ数字に変換して,文字数の変化を調べればOKです。面倒くさい問題のはずが3行で終わってしまいました。