ARC158 C - All Pair Digit Sums (500)
解説の解法
まず繰り上がりの無い場合の解を求めて、繰り上がりの数だけ答えから引く
$ A_iの$ d桁目が繰り上がりによって値が小さくなる場合は全ての$ Aの$ d桁目までをソートしておいて持つと二分探索で求められる
なので各桁毎に各$ A_iとペアになる繰り上がりがその桁の値に影響する個数が$ \mathcal{O}(N \log N)で求まる
問題: https://atcoder.jp/contests/arc158/tasks/arc158_c
提出: https://atcoder.jp/contests/arc158/submissions/39712025
#ARC158 #500pt #C #ARC #AtCoder
#繰り上がり #桁