読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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

Pythonってすごいね。
さすがGoogleの独自言語パイs・・・・じゃなくて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()

まとめ

競技プログラミングでいろんなことを知ってからこれを解いてみたら案外簡単に解けるものが多くて気が抜けた(笑)
17がめんどくさいので今流れがストップしてるけど暇があったらEulerも解いていきたいですね。

とりあえず今はまだPythonの力にたよれちゃってるので