AOJ 0015: National Budget

C++erなので多倍長整数なんてものは知りません。(弱い)

問題概要

原文 → 国家予算 | Aizu Online Judge

80桁まで0以上の整数2つの和を表せ。ただし、計算結果が80桁を超える場合は"overflow"と表示すること。

解説

やり方はわかるんだけどどう書くか迷っちゃう系問題ですよね。ABCのC問題相当でしょうか。

足し算するだけなので、string型とかで読み取って各位ごとに足していって・・・というようにやればよいのですが、そのままだと桁を合わせるのが難しいですね。そこで、reverseで一度数字の文字列を反転します。すると、1の位が0番目に、10の位が1番目に・・・と桁が揃い、扱いやすくなります。

あとはstring型のものをint型に変換するところが書ければ、ほぼできたようなものです。80桁を超えたらoverflowという条件は忘れやすいと思うので注意が必要ですね(1回それ忘れてWA出してしまった)

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int num; cin >> num;
    for(int k = 0; k < num; k++) {
        string s1, s2, ret;
        vector<int> v1, v2;
        cin >> s1 >> s2;

        // s1のほうが長くなるようにする
        if(s2.length() > s1.length()) swap(s1,s2);

        // string 型から1文字ずつ読み取って vector<int> に代入。
        // int 明示的型変換すると ASCII文字コードのあれが返ってくる。1は49なので、48引いて対応する
        for(int i=0; i<s1.length(); i++) v1.push_back((int)s1[i] - 48);
        for(int i=0; i<s2.length(); i++) v2.push_back((int)s2[i] - 48);

        // 桁合わせのためにひっくり返す
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());

        // 各桁について足し算 (n は繰り上がり計算のために必要)
        int n = 0;
        for(int i=0; i<v2.size(); i++) {
            ret += to_string((v1[i] + v2[i] + n) % 10);
            if(v1[i] + v2[i] + n >= 10) n = 1;
            else n = 0;
        }
        // s2の要素がなくなったのでs1の残りを処理
        for(int i=v2.size(); i<v1.size(); i++) {
            ret += to_string((v1[i] + n) % 10);
            if(v1[i] + n >= 10) n = 1;
            else n = 0;
        }

        // "1"を最上位の桁として付加する必要があるかどうか
        if(v1.size() == v2.size() && v1[v1.size() - 1] + v2[v2.size() - 1] + n >= 10) ret += "1";
        else if(v1[v1.size() - 1] + n == 10) ret += "1";

        // 最後にまたひっくり返しておわり
        reverse(ret.begin(), ret.end());
        if(ret.length() > 80) cout << "overflow" << endl;
        else cout << ret << endl;
    }
    return 0;
}