コンテストやってて飽きたので久しぶりにやってみた

Pythonってすごいね。
さすがGoogleの独自言語パイｓ・・・・じゃなくてGuido van Rossum神がつくったPythonですね。

problem 12

1,2,3...と自然数を順に足していった数列1,3,6,10,15...の中で約数が500個を初めて超える数を答えよという問題。
普通に素因数分解して約数の数を調べていくだけだった。

#!/usr/bin/env python
#-*- coding:utf-8 -*-

isp=range(0,1000000)
p=[]

def init():
    for i in range(2, 1000000):
        if isp[i]==i:
            p.append(i)
            for j in range(i*2,1000000,i):
                isp[j]=0

def count(n):
    res=1
    for i in p:
        cnt=0
        if i>n: break
        while n%i==0:
            n/=i
            cnt+=1
        res*=(cnt+1)
    return res

def main():
    init()
    n=0
    res=0
    for i in range(1,1000000):
        n+=i
        if count(n)>=500:
            res=n
            break
    print res

if __name__ == '__main__':
    main()

problem 13

50桁の整数100個を足して、上の10桁を求める問題。
多倍長でごにょごにょ・・・ってやるとCとかでもなんとかできそうだけど、Pythonはどうなのか・・・
調べてみるとPythonの多倍長はメモリの許す限りらしく、結局普通に計算して上10桁コピペでやった
Pythonぱない

#! /usr/bin/env python
#-*- coding:utf-8 -*-
a=[37107287533902102798797998220837590246510135740250L,
46376937677490009712648124896970078050417018260538L,
74324986199524741059474233309513058123726617309629L,
91942213363574161572522430563301811072406154908250L,
23067588207539346171171980310421047513778063246676L,
89261670696623633820136378418383684178734361726757L,
28112879812849979408065481931592621691275889832738L,
44274228917432520321923589422876796487670272189318L,
47451445736001306439091167216856844588711603153276L,
70386486105843025439939619828917593665686757934951L,
62176457141856560629502157223196586755079324193331L,
64906352462741904929101432445813822663347944758178L,
92575867718337217661963751590579239728245598838407L,
58203565325359399008402633568948830189458628227828L,
80181199384826282014278194139940567587151170094390L,
35398664372827112653829987240784473053190104293586L,
86515506006295864861532075273371959191420517255829L,
71693888707715466499115593487603532921714970056938L,
54370070576826684624621495650076471787294438377604L,
53282654108756828443191190634694037855217779295145L,
36123272525000296071075082563815656710885258350721L,
45876576172410976447339110607218265236877223636045L,
17423706905851860660448207621209813287860733969412L,
81142660418086830619328460811191061556940512689692L,
51934325451728388641918047049293215058642563049483L,
62467221648435076201727918039944693004732956340691L,
15732444386908125794514089057706229429197107928209L,
55037687525678773091862540744969844508330393682126L,
18336384825330154686196124348767681297534375946515L,
80386287592878490201521685554828717201219257766954L,
78182833757993103614740356856449095527097864797581L,
16726320100436897842553539920931837441497806860984L,
48403098129077791799088218795327364475675590848030L,
87086987551392711854517078544161852424320693150332L,
59959406895756536782107074926966537676326235447210L,
69793950679652694742597709739166693763042633987085L,
41052684708299085211399427365734116182760315001271L,
65378607361501080857009149939512557028198746004375L,
35829035317434717326932123578154982629742552737307L,
94953759765105305946966067683156574377167401875275L,
88902802571733229619176668713819931811048770190271L,
25267680276078003013678680992525463401061632866526L,
36270218540497705585629946580636237993140746255962L,
24074486908231174977792365466257246923322810917141L,
91430288197103288597806669760892938638285025333403L,
34413065578016127815921815005561868836468420090470L,
23053081172816430487623791969842487255036638784583L,
11487696932154902810424020138335124462181441773470L,
63783299490636259666498587618221225225512486764533L,
67720186971698544312419572409913959008952310058822L,
95548255300263520781532296796249481641953868218774L,
76085327132285723110424803456124867697064507995236L,
37774242535411291684276865538926205024910326572967L,
23701913275725675285653248258265463092207058596522L,
29798860272258331913126375147341994889534765745501L,
18495701454879288984856827726077713721403798879715L,
38298203783031473527721580348144513491373226651381L,
34829543829199918180278916522431027392251122869539L,
40957953066405232632538044100059654939159879593635L,
29746152185502371307642255121183693803580388584903L,
41698116222072977186158236678424689157993532961922L,
62467957194401269043877107275048102390895523597457L,
23189706772547915061505504953922979530901129967519L,
86188088225875314529584099251203829009407770775672L,
11306739708304724483816533873502340845647058077308L,
82959174767140363198008187129011875491310547126581L,
97623331044818386269515456334926366572897563400500L,
42846280183517070527831839425882145521227251250327L,
55121603546981200581762165212827652751691296897789L,
32238195734329339946437501907836945765883352399886L,
75506164965184775180738168837861091527357929701337L,
62177842752192623401942399639168044983993173312731L,
32924185707147349566916674687634660915035914677504L,
99518671430235219628894890102423325116913619626622L,
73267460800591547471830798392868535206946944540724L,
76841822524674417161514036427982273348055556214818L,
97142617910342598647204516893989422179826088076852L,
87783646182799346313767754307809363333018982642090L,
10848802521674670883215120185883543223812876952786L,
71329612474782464538636993009049310363619763878039L,
62184073572399794223406235393808339651327408011116L,
66627891981488087797941876876144230030984490851411L,
60661826293682836764744779239180335110989069790714L,
85786944089552990653640447425576083659976645795096L,
66024396409905389607120198219976047599490197230297L,
64913982680032973156037120041377903785566085089252L,
16730939319872750275468906903707539413042652315011L,
94809377245048795150954100921645863754710598436791L,
78639167021187492431995700641917969777599028300699L,
15368713711936614952811305876380278410754449733078L,
40789923115535562561142322423255033685442488917353L,
44889911501440648020369068063960672322193204149535L,
41503128880339536053299340368006977710650566631954L,
81234880673210146739058568557934581403627822703280L,
82616570773948327592232845941706525094512325230608L,
22918802058777319719839450180888072429661980811197L,
77158542502016545090413245809786882778948721859617L,
72107838435069186155435662884062257473692284509516L,
20849603980134001723930671666823555245252804609722L,
53503534226472524250874054075591789781264330331690L]

def main():
    res=0
    for i in a:
        res+=i
    print res

if __name__ == '__main__':
    main()

problem 14

有名なコラッツの問題、偶数なら2で割って、奇数なら3かけて1足す操作をくりかえして1にするやつ。
あれの続く長さが100万以下でもっとも長くなるような最初の数字を答える問題。
適当にメモ化したらできた

#! /usr/bin/env python
# -*- coding:utf-8 -*-

dp=range(1000000)

def dfs(n):
    if n==1: return 1
    res=0
    if n%2==1:
        temp=dfs(3*n+1)
        if 3*n<1000000:
            dp[3*n]=temp
    else:
        temp=dfs(n/2)
        if n/2<1000000:
            dp[n/2-1]=temp
    return temp+1

def main():
    for i in range(1000000):
        dp[i]=0
    res=1
    rmax=1
    dp[0]=1
    for i in range(1000000):
        if dp[i]==0:
            dp[i]=dfs(i+1)
            if rmax<dp[i]:
                res=i+1
                rmax=dp[i]
    print res

if __name__=='__main__':
    main()

problem 15

単純な組み合わせの問題。
多次元配列の扱いが難しくて、DPでやったらWAだったけど、多倍長の特徴をいかして最終的に愚直に40C20を計算した

#! /usr/bin/env python
# -*- coding:utf-8 -*-
def main():
    res=1L
    for i in range(21,41):
        res*=i
    for i in range(1,21):
        res/=i
    print res

if __name__=='__main__':
    main()

problem 16

2^1000の各桁をすべて足した値を求める問題
多倍長が特殊なので2^1000は普通に計算できる、だからそれを文字列変換して舐めていくだけ

#! /usr/bin/env python
# -*- coding:utf-8 -*-
def main():
    binary=2L**1000
    s=str(binary)
    res=0L
    for i in range(len(s)):
        res+=int(s[i])
    print res,len(s)

if __name__=='__main__':
    main()