JOI2010春合宿day2-A. a+b problem (Lv.8)

考察メモ

次のように手順を分解すると解きやすかったです。
- 入力を扱いやすい形式で受け取る
- 桁上がりなしの形式を作る
- 桁上がりを計算する
- 出力形式を作る
考えた具体例
- 桁上がりが発生する＆桁数が異なる基本ケース
- 1 + 9999のように最後まで繰り返し桁が上がるケース
- 3344+55566のように桁上がりがストップするケース

回答コード(C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

vector<int> A, LA, rLA;
vector<int> B, LB, rLB;
vector<int> a, b;       //桁上がり前の結果. Σ a[i] * (10^b[i] + ... + 10^(b[i + 1] - 1)) (0 <= a[i] <= 18, 0 <= i < a.size()), b.size() = a.size() + 1
vector<int> c;          //桁上がり後の結果. Σ c[i] * (10^b[i] + ... + 10^(b[i + 1] - 1)) (0 <= c[i] <= 9)

void input_number(vector<int> &digits, vector<int> &lengths, vector<int> &rui_lengths) {
    int n;
    cin >> n;
    digits.resize(n);
    lengths.resize(n);
    for (int i = n - 1; i >= 0; i--) {
        cin >> digits[i] >> lengths[i];
    }
    rui_lengths.resize(n + 1);
    rui_lengths[0] = 0;
    for (int i = 1; i <= n; i++) rui_lengths[i] = rui_lengths[i - 1] + lengths[i - 1];
}

void input() {
    input_number(A, LA, rLA);
    input_number(B, LB, rLB);
}

void add_number(vector<int> A, vector<int> rLA, vector<int> B, vector<int> rLB, vector<int> &a, vector<int> &b) {
    int i;
    rep(i, rLA.size()) { b.push_back(rLA[i]); b.push_back(rLA[i] + 1); }
    rep(i, rLB.size()) { b.push_back(rLB[i]); b.push_back(rLB[i] + 1); }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    int j1 = 0, j2 = 0;
    rep(i, (int)b.size() - 1) {
        while (j1 < rLA.size() && rLA[j1] <= b[i]) j1++;
        while (j2 < rLB.size() && rLB[j2] <= b[i]) j2++;
        int d1 = (j1 >= rLA.size()) ? 0 : A[j1 - 1];
        int d2 = (j2 >= rLB.size()) ? 0 : B[j2 - 1];
        a.push_back(d1 + d2);
    }
}

//convert: (a, b) -> (c, b)
void carry(vector<int> &a, vector<int> &b, vector<int> &c) {
    int i;
    c.resize(b.size());
    rep(i, a.size()) {
        c[i] += a[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
}

void create_output_format(vector<int> &c, vector<int> &b, vector<int> &digits, vector<int> &lens) {
    int n = c.size(), i;
    int len = 0;
    assert(b.size() == n);

    rep(i, n) {
        if (i > 0 && c[i - 1] != c[i]) {
            digits.push_back(c[i - 1]);
            lens.push_back(len);
            len = 0;
        }
        if (i + 1 < n) len += b[i + 1] - b[i];
        else len++;
    }
    digits.push_back(c[n - 1]);
    lens.push_back(len);

    for (i = (int)digits.size() - 1; i > 0 && digits[i] == 0; i--);
    digits.resize(i + 1);
    lens.resize(i + 1);
}

void output(vector<int> &digits, vector<int> &lens) {
    cout << digits.size() << endl;
    assert((*digits.rbegin()) > 0);
    for (int i = (int)digits.size() - 1; i >= 0; i--) {
        cout << digits[i] << " " << lens[i] << endl;
    }
}

signed main() {
    input();
    add_number(A, rLA, B, rLB, a, b);
    carry(a, b, c);
    vector<int> digits, lens;
    create_output_format(c, b, digits, lens);
    output(digits, lens);
    return 0;
}

回答コード(Python)

from typing import List, Tuple

class JOIsp2010Day2A:
    def __init__(self):
        # 下の桁からA[0]がLA[0]桁, A[1]がLA[1]桁, ...の形式. rLA[0]=0, rLA[i]=LA[0]+...+LA[i-1].
        self.A: List[int] = []
        self.LA: List[int] = []
        self.rLA: List[int] = []
        self.B: List[int] = []
        self.LB: List[int] = []
        self.rLB: List[int] = []
        
    def input_number(self) -> Tuple[List[int], List[int], List[int]]:
        n = int(input())
        digits: List[int] = [0] * n
        lengths: List[int] = [0] * n
        for i in reversed(range(n)):
            digits[i], lengths[i] = map(int, input().split())
        rui_lengths: List[int] = [0] * (n + 1)
        for i in range(1, n + 1):
            rui_lengths[i] = rui_lengths[i - 1] + lengths[i - 1]
        return digits, lengths, rui_lengths


    def input(self) -> None:
        self.A, self.LA, self.rLA = self.input_number()
        self.B, self.LB, self.rLB = self.input_number()
    
    # return: 桁上がりを忘れて、A + B = Σ a[i] * (10^b[i] + ... + 10^(b[i + 1] - 1)) (i=0,...,len(a)-1), len(b) = len(a) + 1の形式にする。
    def add_number(self, A: List[int], rLA: List[int], B: List[int], rLB: List[int]) -> Tuple[List[int], List[int]]:
        b: List[int] = []
        b.extend(rLA)
        b.extend(rLB)
        b.extend([item + 1 for item in rLA])
        b.extend([item + 1 for item in rLB])
        b = sorted(list(set(b)))
        
        j1: int = 0
        j2: int = 0
        a: List[int] = []
        for i in range(len(b) - 1):
            while j1 < len(rLA) and rLA[j1] <= b[i]:
                j1 += 1
            while j2 < len(rLB) and rLB[j2] <= b[i]:
                j2 += 1
            d1: int = 0 if j1 >= len(rLA) else A[j1 - 1]
            d2: int = 0 if j2 >= len(rLB) else B[j2 - 1]
            a.append(d1 + d2)
        return a, b
    
    # convert: (a, b) -> (c, b), return: c
    def carry(self, a: List[int], b: List[int]) -> List[int]:
        c: List[int] = [0] * len(b)
        for i in range(len(a)):
            c[i] += a[i]
            c[i + 1] += c[i] // 10
            c[i] %= 10
        return c
    
    def create_output_format(self, c: List[int], b: List[int]) -> Tuple[List[int], List[int]]:
        n: int = len(c)
        length: int = 0
        assert len(b) == n
        
        digits: List[int] = []
        lens: List[int] = []
        for i in range(n):
            if i > 0 and c[i - 1] != c[i]:
                digits.append(c[i - 1])
                lens.append(length)
                length = 0
            if i + 1 < n:
                length += b[i + 1] - b[i]
            else:
                length += 1
        digits.append(c[n - 1])
        lens.append(length)
        
        i: int = len(digits) - 1
        while True:
            if digits[i] > 0:
                break
            i -= 1
        digits = digits[:i + 1]
        lens = lens[:i + 1]
        return digits, lens
    
    def output(self, digits: List[int], lens: List[int]) -> None:
        print(len(digits))
        for i in reversed(range(len(digits))):
            print(f"{digits[i]} {lens[i]}")
    
    def solve(self) -> None:
        self.input()
        a, b = self.add_number(self.A, self.rLA, self.B, self.rLB)
        c = self.carry(a, b)
        digits, lens = self.create_output_format(c, b)
        self.output(digits, lens)

if __name__ == '__main__':
    solver = JOIsp2010Day2A()
    solver.solve()