Numeral System 解説

問題名：Numeral System (PKU)
出典：Problem C, ACM/ICPC Japan Domestic, 2005-07-01
難易度：☆
問題の種類：文字列操作
解法：特になし
解答ソースコード：
- 2685-deq.cpp

アルゴリズムの概略

MCXI形式という文字列が2つ与えられるので，それをいったん数値に変換して和をとってから，再度MCXI形式に変換して出力します。

数値への変換は，最初は結果 result = 0 としておいて，文字列を前から見ていって値を足し合わせていけばOKです。数字がなければ d = 1，数字があれば d = str[i] - '0' としておいて，続く文字が 'm' であれば result += 1000 * d という感じで足していけば求まります。

MCXI形式への変換は，大きい数字から（最初は'm'から）順に見ていけばOKです。例えば 9100 であれば 1000 の桁は 9 なので "9m" を出力し，次に 100 の桁は 1 なので "c" を出力します。 1の場合は数字を出力しないように，0の場合は何も出力しないようにするだけです。

アルゴリズムの計算量

計算量は線形（オーダーが入力文字列の長さ n に対して O(n) となる）なので問題となりません。

アルゴリズムの実装

特にありませんが，各桁の文字の情報は

char c[4] = {'m', 'c', 'x', 'i'}; // characters
int v[4] = {1000, 100, 10, 1}; // values

という風に持っておいてループを回すとプログラムの行数が短くなります。また，数値から文字列への変換時は，いったん文字列に結果を求めてから出力するよりも，求まった瞬間に出力していった方がプログラムが簡単になります。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $

deq notes