TopCoder Open Round 1B Easy: TheNicePair

TCOR1Bに参加。Easy提出ACと7Hack1Missで187位。1190 → 1292 (+102)でようやくDiv1に到達。

問題

N(≦ 50)個の正の整数からなる数列A(A_i ≦ 1000)が与えられる。この数列のある範囲の部分数列を考える。この部分数列に含まれる数のうち半分以上を割り切る2以上の数が存在するなら、この部分数列を有効であると考える。有効な部分数列の長さの最大値を答えよ。

解法

A_iが1000と小さいので全探索で答えを得られる。2以上の数について、数列中のA_iから順番に割る切るどうかをカウントしていく。カウントが範囲の半分以上の場合、有効な部分数列なので、その長さの最大値を取っていく。

def solve(self, A):
    n = len(A)
    ans = -1
    for mod in xrange(2, 1001):
        for i in xrange(n):
            cnt = 0
            for j in xrange(i, n):
                if A[j] % mod == 0: cnt += 1
                if 2 * cnt >= j - i + 1:
                    ans = max(ans, j - i)
    return ans

本番ではA_iの最大値をなぜか100000ぐらいに勘違いしていた。そのため全探索は無理と考えたので別解で解いた。下のコードは、まず約数を全列挙してから、部分数列中に半分以上含まれる約数があるかどうかで有効かどうかを確認している。問題分をよく読まないと（N回目）。

def getFact(n):
    fact = []
    i = 2
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n /= i
            cnt += 1
        if cnt > 0: fact.append([i, cnt])
        i += 1
    if n > 1: fact.append([n, 1])
    res = set([1])
    while 1:
        nres = res.copy()
        for i in xrange(len(fact)):
            a, p = fact[i]
            if p == 0: continue
            for j in res:
                nres.add(j * a)
            fact[i][1] -= 1
        if res == nres:   break
        res = nres.copy()
    return list(res)

def solve(self, A):
    n = len(A)
    A = [getFact(a) for a in A]
    ans = -1
    for i in xrange(n):
        for j in xrange(i + 1, n + 1):
            hist = collections.defaultdict(int)
            for a in A[i:j]:
                for k in a:
                    hist[k] += 1
            for k, v in hist.items():
                if k == 1: continue
                if 2 * v >= j - i:
                    ans = max(ans, j - i - 1)
                    break
    return ans