唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder Open 2015 Round 2A x-- 1232->1232

例のごとく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)))