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

ゆらのふなびと

競プロ, Python, C++

ARC043 B - 難易度 (作成中)

記事書こうと思ったんですけど,やっぱりわかってないということがわかったので記録だけ残しておきます.

問題

 N 個の正の整数  D_1, ..., D_N から, D_i \geq 2 D_{i-1} (i=1, 2, 3) を満たすような4つの要素を選ぶ方法は何通りか. 10^{9}+7 で割った余りを求めよ.

制約

 4 \leq N \leq 10^{5}

 1 \leq D_i \leq 10^{5}

解法

ここでは公式の解説とは異なる方法を採用する.DPである.

dp[i][j] = (0番目からi番目までの数を,j以下の数から選ぶ方法)とすると,以下のように計算できる.(←この解釈であってる???)

MOD = 10**9 + 7
MAX_D = 10**5 + 1 + 1
NUM_PROBLEMS = 4
 
N = int(input())
 
#dp[i][j]: num of ways to choose 0..i-th number within [0, j] 
dp = [ [0] * MAX_D for _ in range(NUM_PROBLEMS)]
for _ in range(N):
    x = int(input())
    for i in range(NUM_PROBLEMS):
        dp[i][x] += 1
 
for i in range(NUM_PROBLEMS):
    for j in range(MAX_D):
        #cumulative sum
        dp[i][j] += dp[i][j-1]
        dp[i][j] %= MOD
    
    if i >= 3:
        break
        
    for j in range(MAX_D):
        #choose (i+1)-th number x s.t. x >= 2*(i-th number)
        dp[i+1][j] *= dp[i][j // 2]
        dp[i][j] %= MOD
 
print(dp[-1][-1])