TopCoder Open 2015 Round 1B o-- 1225->1266

微妙な順位でRound1を通過した

312位, 228.26点, +1/-0 challenge
Volatility: ?->255

• TCO15 Algorithm R1B - Togetterまとめ

250: TheNicePair

整数のリストが与えられるので、そこから任意の範囲を選んだ時に範囲内の半分以上の整数が1以外の同じ数で割り切れる最大の範囲の長さ引く1を答える
条件を満たさない場合は-1と答える

すべての範囲とすべての数で割るのを試しても間に合うっぽい

長さが1の時に必ず-1と答えるコードの人がいたので1撃墜できた

下記のコードは最初にありうる素因数の列挙をしてからやってる

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def prime_factor_table(n):
    table = [0] * (n + 1)
    
    for i in xrange(2, n + 1):
        if table[i] == 0:
            for j in xrange(i + i, n + 1, i):
                table[j] = i
    
    return table

def prime_factor(n, prime_factor_table):
    prime_count = collections.Counter()
    
    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n /= prime_factor_table[n]
    prime_count[n] += 1
    
    return prime_count

class TheNicePair:
    def solve(self, A):
        L = len(A)
        P = prime_factor_table(1002)
        print
        p = []
        for i in xrange(L):
            p.append(prime_factor(A[i], P))
        result = -1
        divisor = set()
        for d in p:
            for div in d:
                divisor.add(div)
        for i in xrange(L):
            for div in divisor:
                if div == 1:
                    continue
                count = 0
                length = 0
                for j in xrange(i, L):
                    length += 1
                    if div in p[j]:
                        count += 1
                    if count * 2 >= length and result < j - i:
                        result = j - i
        return result

500: TheTips

N個のものが見つかる確率\(probability\)が与えられる
またi番目のものが見つかったら必ずある他の要素が見つかる関係が定義されていて、そのリストも与えられる
何個が見つかるかの期待値を答える

確率を求めて期待値の線形性でやるだけ、と思ったら2回以上の連鎖で見つかる場合を考慮してなくて本番中には解けなかった

i番目のものを連鎖して見つける可能性のあるものをDFSやワーシャル・フロイド的なアルゴリズムであらかじめ列挙しておく
他から連鎖的に見つかる場合も含めてi番目が見つかる確率は、1マイナスi番目が見つからない確率なので、i番目を連鎖して見つける可能性のあるものについてそれぞれ見つからない確率をかけて、1から引けばよい

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class TheTips:
    def solve(self, clues, probability):
        L = len(clues)
        result = 0.0
        probability = list(probability)
        for i in xrange(L):
            probability[i] /= 100.0
        
        clues = list(clues)
        for k in xrange(L):
            for i in xrange(L):
                clues[i] = list(clues[i])
                for j in xrange(L):
                    if clues[i][k] == clues[k][j] == 'Y':
                        clues[i][j] = 'Y'
        
        for i in xrange(L):
            prob = 1.0
            for j in xrange(L):
                if i == j:
                    prob *= (1 - probability[j])
                elif clues[j][i] == 'Y':
                    prob *= (1 - probability[j])
            result += (1 - prob)
        return result