競技プログラミング風 C++問題集【第13回】

・文字列の文字はメモリ内では数字で表される。例えば、UTF-8, ASCII などでは ‘0’ は0x30 だ。
・’1′, ‘2’, … ‘9’ には連続的な数字で表されるので、文字 ch を数値に変換するには ch – ‘0’ とするとよい。
・上記を考慮して下位の桁から順番に加算していくんだぞ。

#if 1
string add(const string& x, const string& y) {
    auto mxl = max(x.size(), y.size());
    string ans(mxl, ' ');
    int carry = 0;      //  桁上りの場合は 1
    auto ix = x.rbegin();       //  下位の桁から計算するので逆イテレータを使用
    auto iy = y.rbegin();       //  同上
    for(auto itr = ans.rbegin(); itr != ans.rend(); ++itr) {    //  答えも下位の桁から順に計算
        char cx = ix != x.rend() ? *ix++ : '0';
        char cy = iy != y.rend() ? *iy++ : '0';
        *itr = cx + cy - '0' + carry;
        if( *itr > '9' ) {      //  桁上りの場合
            carry = 1;
            *itr -= 10;         //  1X → X
        } else
            carry = 0;          //  桁上りなし
    }
    if( carry )     //  桁上りが残っていた場合
        ans = '1' + ans;
    return ans;
}
#else
string add(const string& x, const string& y) {
    auto mxl = max(x.size(), y.size());
    string ans(mxl, ' ');
    int carry = 0;      //  桁上りの場合は 1
    auto px = &x[0] + x.size();
    auto py = &y[0] + y.size();
    for(auto ptr = &ans[0] + ans.size(); ptr != &ans[0]; ) {    //  答えも下位の桁から順に計算
        char cx = px != &x[0] ? *--px : '0';
        char cy = py != &y[0] ? *--py : '0';
        *--ptr = cx + cy - '0' + carry;
        if( *ptr > '9' ) {      //  桁上りの場合
            carry = 1;
            *ptr -= 10;         //  1X → X
        } else
            carry = 0;          //  桁上りなし
    }
    if( carry )     //  桁上りが残っていた場合
        ans = '1' + ans;
    return ans;
}
#endif

結果を格納する文字列 ans を用意しておく。長さは加算する文字列の桁数の多い方の長さに設定しておく。 最後に桁上りがなければそれが答えの長さとなる。
加算は下位の桁から順に計算していくので、rbegin() をにより逆イテレータを取得・使用する。
以上を先頭文字まで繰り返す。最後の桁で桁上りがあった場合は、答え文字列の先頭に ‘1’ を付加する。そして結果文字列をリターンする。

逆イテレータには慣れてなくて難しいという人もいるかもしれないので、 通常のポインタを使用する版も解答例の #if でコメントアウトされた部分に示しておく。

・文字列の文字はメモリ内では数字で表される。例えば、UTF-8, ASCII などでは ‘0’ は0x30 だ。
・’1′, ‘2’, … ‘9’ には連続的な数字で表されるので、文字 ch を数値に変換するには ch – ‘0’ とするとよい。
・上記を考慮して上位の桁から順番に乗算していくんだぞ。

string mul(const string& m, char c) {   //  任意精度整数と1文字を乗算
    if( c == '0' || m == "0" ) return "0";      //  どちらかが0の場合
    c -= '0';   //  '0'～'9' を 0～9 に変換
    string ans(m.size(), ' ');
    auto im = m.rbegin();   //  逆イテレータ、下位の桁から順に乗算するため
    int carry = 0;      //  桁上り
    for(auto itr = ans.rbegin(); itr != ans.rend(); ++itr) {
        int t = (*im++ - '0') * c + carry;      //  乗算＋桁上り
        carry = t / 10;     //  桁上り
        *itr = (t % 10) + '0';      //  ひとけた目の数値を文字に変換し格納
    }
    if( carry != 0 )        //  桁上りがあった場合
        ans = (char)(carry + '0') + ans;
    return ans;
}
string mul(const string& x, const string& y) {
    string ans = "0";   //  積和のための文字列
    for(auto itr = y.begin(); itr != y.end(); ++itr) {  //  上位桁から順に乗算
        auto t = mul(x, *itr);
        ans = add(ans + '0', t);    //  以前の積和を10倍し、１桁の乗算結果を加える
    }
    return ans;
}

まずは、任意精度整数と1文字を乗算する string mul(const string& m, char c) を実装する。
m が “0” または c が ‘0’ であれば、乗算結果は 0 なので、”0″ を返す。
c -= ‘0’ で、数字文字を数値に変え、m の下位桁から順に、桁上りを考慮しつつ乗算していく。

1文字との乗算が出来上がれば、任意精度整数同士の乗算は簡単だ。 答えを入れる変数 ans を用意しておき、乗数の上位から順に被乗数に先の mul() 関数を使って乗算を行い、 ans を10倍しながら、結果を ans に足し込んでいく。全桁の乗算が終われば答えを返すだけだ。