gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

AOJ Numeral System 解説

問題
Numeral System | Aizu Online Judge

解説

方針としては、文字列を読み込んで、数字に直し、足し算した後で再びMCXI文字列に直します。

まずは、読み込んだ文字列をどう処理するかを考えます。
まず、1000,100,10,1の時は、m,c,x,i の文字が単体で置かれます。
2000や500のような時は、2mや5cのように数字が文字の左側につきます。

この法則から、文字列を読み込んで前から順番に見ていく中で、i番目が数字であれば、その次に必ず文字が来ることが分かります。つまり、i+1番目が必ず配列外参照になりません。
よって、数字が来れば、その次の文字も見て、掛け算で値を取り出すことができます。この時、i++として追加でiを進めることで、i+1番目の文字を再度見ないようにします。

i番目が文字の時、それは単体で存在していることがわかります。もし左側に数字があれば、それは前述の処理で飛ばされているはずです。
この時は、普通に文字を数字に変換します。

次に足し算をした後にMCXI文字列に戻す作業を考えます。
ここでも、m,c,x,iに対応した位を見て、「0」,「1」,「それ以外」の3つのパターンで場合分けします。
1000の位を見たければ1000で割るだけで取り出せることに注意しつつ、0なら何もなし、1ならそのまま文字を出力、それ以外なら数字と文字を続けて出力します。

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)

using namespace std;

//文字を数字に変換する関数
int chan(char c){
    if(c=='m')return 1000;
    if(c=='c')return 100;
    if(c=='x')return 10;
    if(c=='i')return 1;
}
 
int main(){
    int n;
    cin>>n;
    rep(p,0,n){
        int num[2]={0};  //num[0],num[1]は1つ目、2つ目の文字列の値を表す
        rep(j,0,2){  //2つの文字列について処理
            string s;
            cin>>s;
            rep(i,0,s.length()){
                if('0'<=s[i] && s[i]<='9'){ //i番目が数字なら、i+1番目をみる
                    num[j]+=(s[i]-'0')*chan(s[i+1]);
                    i++;
                }else { //i番目が文字なら、そのまま数字に
                    num[j]+=chan(s[i]);
                }
            }
        }
        
        int ans=num[0]+num[1];  //足し算する
  
        //以下が出力部で、各位の値を見て出力を場合分け
        if(ans/1000==1)cout<<'m';
        else if(ans/1000!=0)cout<<ans/1000<<'m';
        ans%=1000;
        
        if(ans/100==1)cout<<'c';
        else if(ans/100!=0)cout<<ans/100<<'c';
        ans%=100;
        
        if(ans/10==1)cout<<'x';
        else if(ans/10!=0)cout<<ans/10<<'x';
        ans%=10;

        if(ans==1)cout<<'i';
        else if(ans!=0)cout<<ans<<'i';
        cout<<endl;
        
    }
    return 0;
}