TopCoder SRM 632 Div2 oox 1134->1226

42th, 725.99pts, +1/-0 challenge
Volatility: 451->450

Div1 復帰した。久しぶりにchallenge成功
Hardはあまり自信ないのを投げたら予想通りSystem Testで落ちた

250: RunningAroundPark

木に1からNの番号が付いている
ランニング中に見た木の番号が途中抜けありで与えられるので、最小何周しているか答える

木の番号が前の番号以下になった回数を答えれば良い

class RunningAroundPark:
    def numberOfLap(self, N, d):
        lap = 1
        L = len(d)
        if len(d) == 1:
            return 1
        p = d[0]
        for i in d[1:]:
            if p >= i:
                lap += 1
            p = i
        return lap

500: PotentialGeometricSequence

ある数列について、それぞれの数を2進数で表した時の末尾の0の数の数列が与えられる
元の数列の連続した部分が等比数列になっている可能性がある部分の数を答える

元の数は2のn乗であると考えた時一番等比数列になりやすいので、末尾の0の数が等差数列になっている部分の数を数えればよい

class PotentialGeometricSequence:
    def numberOfSubsequences(self, d):
        L = len(d)
        if L == 1:
            return 1
        print
        ret = L
        diff = [0] * (L - 1)
        for i in xrange(L - 1):
            diff[i] = d[i + 1] - d[i]
        
        M = L - 1
        for i in xrange(M):
            c = diff[i]
            for j in xrange(i, M):
                if diff[j] == c:
                    ret += 1
                else:
                    break
        
        return ret

1000: GoodSubset

ある値\(goodValue\)と整数値の集合\(d\)が与えられるので、\(d\)の部分集合の積が\(goodValue\)になる組み合わせの数を答える

てきとーなメモ化探索を投げたらSystem Testで死んでた

最大ケースを投げるとTLEになる人がいたので一人落とした

以下のコードは正解するコード
何故かsys.setrecursionlimit()で再帰の最大数を上げ忘れると死ぬ

import math,string,itertools,fractions,heapq,collections,re,array,bisect,copy

class GoodSubset:
    def numberOfSubsets(self, goodValue, d):
        import sys
        sys.setrecursionlimit(10000)
        class memoize(dict):
            def __init__(self, func):
                self.func = func

            def __call__(self, *args):
                return self[args]

            def __missing__(self, key):
                result = self[key] = self.func(*key)
                return result

        d = list(d)
        d.sort(reverse = True)
        rate = 1
        
        candidate = []
        for v in d:
            if v == 1:
                rate *= 2
            else:
                candidate.append(v)
        
        if goodValue == 1:
            return (rate - 1) % 1000000007
        
        L = len(candidate)
        print
        @memoize
        def solve(i, value):
            if value == 0:
                return 0
            if i >= L:
                if value != 1:
                    return 0
                else:
                    return 1
            
            ret = 0
            ret += solve(i + 1, value)
            if value % candidate[i] == 0:
                ret += solve(i + 1, value / candidate[i])
            return ret % 1000000007
        
        return (solve(0, goodValue) * rate) % 1000000007