syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(3問目)

問題
Pollock's Conjecture

所感
・はじめての動的計画法
・任意の整数を扱う問題が出たら基本的にDP使うんか?
・わしには難しかったょ(そもそもRuntimeError)
・DP使っても1分45秒かかってるのでゴミ

解法
・正四面体数を使って106のリストを更新していく
・できたリストを入力数字に対して返す

コード

def pollockConjecture():
    inf=int(1e6)
    dp=list(range(0,inf+1))
    odp=list(range(0,inf+1))
    n=2
    s=1
    os=1
    while s<inf+1:
        s=n*(n+1)*(n+2)//6
        n+=1
        if s%2==1:
            os=s
        for i in range(0,inf+1-s):
            dp[i+s]=min(dp[i+s],dp[i]+1)
            odp[i+os]=min(odp[i+os],odp[i]+1)
    return dp,odp

if __name__=="__main__":
    dp,odp=pollockConjecture()
    while True:
    N=int(input())
    if N==0:
        break
    print(dp[N],odp[N])

pythonおそうい

参考元:
http://yoshiki-utakata.hatenablog.com/entry/2015/05/21/140023