"Chokudai Contest 002: A - 約数をたくさんつくろう！"で実装したやつ

chokudai002_a.py

# encoding: utf-8

# problem: http://chokudai002.contest.atcoder.jp/tasks/chokudai002_a
# Score: 37616 (http://chokudai002.contest.atcoder.jp/submissions/964911)
from math import sqrt
import random

base = 2*3*5*7*11*13*3*3
N = 100
M = 10000
prime = [1]*M
prime[0] = prime[1] = 0
for i in xrange(2, int(sqrt(M))+1):
    if prime[i]:
        for j in xrange(i*i, M, i):
            prime[j] = 0
random.seed()

# 100個の整数生成
def maker():
    pocket = [base]*N

    for i in xrange(2, M):
        if prime[i]:
            a = range(N)
            random.shuffle(a)
            for j in a:
                if pocket[j]*i <= 10**9:
                    pocket[j] *= i
                    break
            else:
                break
    for i in xrange(N):
        while pocket[i]*2 <= 10**9:
            pocket[i] *= 2
    return pocket

# 得点計算
def solver(P):
    dic = {}
    ans = 0
    for e in P:
        res = 1
        ept = 1
        i = 2
        while e>1:
            if e % i == 0:
                cnt = 0
                while e%i == 0:
                    e /= i
                    cnt += 1
                res *= (cnt+1)
                if i in dic:
                    ept *= (min(cnt, dic[i])+1)
                dic[i] = max(cnt, dic.get(i, 0))
            i += 1
        ans += res - ept
    return ans+1

ma = 0
mP = [0]*100
try:
    while 1:
        P = maker()
        res = solver(P)
        if ma < res:
            print "->", res
            ma = res
            mP = P
except KeyboardInterrupt, e:
    # Ctrl+C
    print "Score :", ma
    for e in mP:
        print e