きろく

特筆すべき記録のまとめ

JOI '10 春合宿2:1- 足し算 (a+b problem)

問題

https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf

解法

小さい位から順に考えていく.桁を1つ1つ見ていては TLE になってしまうので,1つ目か2つ目の整数の桁の数が変わる桁の位置で区切って考える.1つの区間は xx...xy のように一番小さい桁のみが他の桁と異なる数となる.これを愚直に実装すればよい.区間間で繰り上がりの処理をする必要がある場合があるので気を付ける.O(mlogm).

解答

atcoder.jp

区間の長さが 0 であるケースと一番大きな桁への繰り上がりの処理を考えておらず 1 WA してしまった.

f:id:babcs2035:20190131214726p:plain