【ABC178 D】「Redistribution」を解く【Python3】

コンテスト一覧へ

 

すべての項が3以上の整数で、総和が整数Sであるような数列がいくつあるのか、を求める問題です。

提出
s = int(input())
mod = 10**9+7
dp = [0]*(s+1)
dp[0] = 1

for i in range(1,s+1):
    for j in range(0,(i-3)+1):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[s])

DP(動的計画法)という方法で解いていきます。

整数S=7の場合、区切られる位置は、

|○○○○○○○|
|○○○|○○○○|
|○○○○|○○○|

の {7}, {3,4}, {4,3} が条件を満たすため、答えは3になります。

 

この区切る位置に注目します。

最後に区切る位置をiとしたときの数列の個数dp[i]を求めます。

例えば、「i=3」である場合、

|○○○|○……

となるため、dp[3]=1になります。「i=4」では、

|○○○○|○……

となり、dp[4]=1となります。

「i=7」の場合、

|○○○○○○○|○……

と、「dp[3]+dp[4]」を加えたものが答えになり、dp[7]=3となります。

最後の区切り位置より左側には、3つ以上の◯がないといけないので、「0≦j≦4」のdp[j]を足し合わせる形になります。

(dp[1]とdp[2]は、ともに0です)

 

提出したプログラムに話を戻します。

すべてのdpに初期値0を代入します。

dp[0]は、1にしておきます。

特定のdp[i]を求めるために、「0≦j≦(i-3)」のdp[j]を使用します。

最終的にdp[s]に入っている数値が答えです。

【ABC178】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。