整数をローマ数字に

大きい記号から削っていくと、4 が IIII になる

1994 をローマ数字にしたいとき、まず M を 1 つ取って 994、次に D を取って 494、と大きい記号から順に引いていく手が思い浮かびます。実際この方針で 3 は III、58 は LVIII と正しく出ます。

つまずくのは 4 と 9 です。4 は I を 4 回並べて IIII になってしまいます。正解は IV で、同じ記号を 4 回続けて書くことは許されていません。

貪欲がうまくいく表と、いかない表

大きいほうから取れるだけ取る、という進め方を貪欲法と呼びます。日本の硬貨で 380 円を作るときは、100 円を 3 枚、50 円を 1 枚、10 円を 3 枚と大きい順に選ぶだけで必ず最小枚数になります。

ところが額面が 1, 3, 4 のような並びだと話が変わります。6 を作るとき、貪欲では 4 + 1 + 1 の 3 枚になりますが、正解は 3 + 3 の 2 枚です。第 6 章の硬貨の問題を動的計画法で解いたのは、こうした額面では貪欲が成立しないからでした。

ローマ数字の記号を 7 個のまま使うと、まさにこの「成立しない表」になります。4 と 9 のところで詰まるからです。逆に言えば、この問題の設計判断は 1 つだけで、貪欲が成立するように表のほうを作り替えられないか、という点に絞られます。4 と 9 の位置に現れる 2 文字の並びを、2 文字としてではなく 1 つの記号として表に混ぜてしまえば、あとは大きいほうから取れるだけ取るだけになります。

同じ記号は 3 回続くことがある

表から 1 つ選んで 1 回引く、という書き方だと 3000 が M 1 つで止まります。MMM にするには、その記号が引けなくなるまで引き続ける必要があります。逆に 4 回以上続くことは、表を作り替えた後なら起こりません。

つまり外側は表を上から順に見るだけ、内側は同じ記号を使い切るまで、という二段構えになります。

表の並び順も効いてきます。大きいほうから見ていないと、1000 に対して 500 の記号を 2 つ当ててしまいます。作った表を上から読み直して、値が単調に減っているかを一度確かめてください。

なお、外側は表の行数ぶんしか回らず、内側も同じ記号が 4 回以上続かないので、入力の大きさによらず反復回数は一定です。num が 1 でも 3999 でも、かかる時間はほとんど変わりません。計算量を O(1) と書ける、めずらしい部類の問題です。

前のレッスンと合わせて、同じ対応関係を両方向に実装したことになります。片方は隣を見比べる走査、もう片方は表を上から削る貪欲。同じ題材でも、変換の向きが変わるだけで使う道具がまるごと入れ替わるのは、覚えておく価値があります。

やってみよう

intToRoman(num) を実装してください。num は 1 から 3999 までの整数です。貪欲法を使い、対応するローマ数字の文字列を返してください。

1. 関数 intToRoman(num) を実装し、ローマ数字文字列 を返す
2. 減算表記 を含む 13 個の値表を使い、貪欲法 で削っていく
3. 値表は 大きい順 に並べ、while num >= value で同じ記号を必要回数追加する