a + b problem(足し算) - joi2010-day2 解説

筆者: qnighy

大きな自然数a,bがランレングス圧縮されて与えられるとき、a+bを計算して再びランレングス圧縮して出力する問題である。

O(ML)解法

明らかなのは、ランレングス圧縮を伸長して通常の多倍長数値にし、加算した後再びランレングス圧縮する方法である。

この方法であれば、桁数に比例する時間およびメモリでできるので、30点が期待できる。

O(M)解法

ランレングス圧縮ということは、同じ数字の並びが非常に多いことが予想される。同じような桁の並んだ数の和には規則性がありそうだと予想されるので、そのことを考えればよい。

調べてみると、上下それぞれ同じ数字の並びになっている区間は、最も下の1桁以外は和の各桁も同じになることがわかる。(例. 99999+88888=188887)

このことを念頭に置けば、答えの数字における桁の変化点をO(M)個に絞り込むことができる。

あとは通常通り繰り上がりのある筆算を行うようにプログラムを書けば満点が期待できる。

実装の手間は極力避けたいので、どのように実装するのが全体として効率良くなるかを考えてから実装するとよいだろう。