例のごとく1問も解けずorz
382位, 0点, +0/-0 challenge
Volatility: 241->218
250: ModModMod
正の整数の配列\(m\)と正の整数\(R\)が与えられる
ただし\(m\)のすべての要素について\(1 \le m[n] \le 5000\)、また\(1 \le R \le 10000000\)
\(1\)から\(R\)までのすべての数値について、\(m\)の要素すべてで順に\(\bmod \)をとった値の総和を求める
つまり\(\sum_{i=1}^R (((i \bmod m[0]) \bmod m[1]) \dots \bmod m[N - 1])\)
本番では解けず
\(R\)までのすべての数値についてどの数値が何個残っているかのリストを下記のような更新式で更新していけばよい
\(\mathrm{count}[i \bmod m[n]] = \mathrm{count}[i]\)
これは\(m[n]\)が今までに\(\bmod\)の方になった最大の数よりも小さくなった時にその間の数についてだけ更新される
たかだか\(R\)回しか更新されないので計算量は\(O(R)\)ぐらい
Practice roomでリスト内包表記で書いたらメモリの制限をオーバーして(?)エラーを吐いたのでジェネレータ式で書いたら通った(たまたまTopCoderのシステムの調子が悪かったのかも
class ModModMod: def findSum(self, m, R): count = [1] * (R + 1) ub = R for i in m: if ub < i: continue next = i - 1 for j in xrange(next + 1, ub + 1): count[j % i] += count[j] ub = next return sum((i * count[i] for i in xrange(ub + 1)))