AtCoder ABC169 F問題 実行速度向上の方法 (動的計画法)

Question

前提・実現したいこと

AtCoder ABC169 F問題に関する質問です。
下記のプログラムを作成しましたが、TLEとなってしまいました。
どこを修正すれば良いかをお聞きしたいです。
27testfile中7WAとなっているようで、問題文中のtestfileに関しては正常に作動しました。

発生している問題・エラーメッセージ

TLE 時間超過

該当のソースコード

n,s = map(int, input().split())
a = list(map(int, input().split()))

MOD = 998244353

dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる 参照渡しによるバグを防ぐためリスト内包表記
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

print(dp[n][s])

試したこと

12行目について
dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD
↓
dp[i+1][ss] = (dp[i][ss]*2%MOD + dp[i][ss-a[i]])%MOD
としましたが、逆にTLEとなるケースが2つ増えてしまいました。

##以降はyudedaka67様のご回答を参考にさせていただき試した修正

二重配列の廃止

...
dp = [[0]*(s+1) for i in range(n+1)] #動的計画法を用いる 参照渡しによるバグを防ぐためリスト内包表記
↓
dp = [0]*(s+1)

ループ部分を以下に変更
for i in range(n):
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            dp[ss] = (dp[ss]*2 + dp[ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[ss] = dp[ss]*2 % MOD

→TLEとなるファイルが7から5に

###Numpyの導入
######numpy.zerosによるベクトル生成
これだけだと逆にimportする分TLEが増えてしまいました
######numpyのベクトルの整数倍を用いる

...for　iの中身を修正
ddp = dp * 2
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            ddp[ss] += dp[ss-a[i]]%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
    dp = ddp % MOD

これでもTLEとなるようでした

######numpyのベクトルの加算を用いる

...for　iの中身を修正
ddp = dp * 2 % MOD
ddp[a[i]:] += dp[:-a[i]] #非常に大きな数になると考えられるため先にMOD計算を行う
dp = ddp % MOD

こうすることで1/S倍ほどになり、ACできました。

Comments

[set0gut1]

処理系を python から pypy に変えるだけで定数倍速くなって AC することあるのでちょっと試してみてください。

[shake9]

PyPyでも提出できるのですね、ありがとうございます、ACできました！
まさか実行時間が1/10になるとは…勉強になりました。

[set0gut1]

回答してる方の「Python自体の遅さの問題」ってのが本質情報でしたね

Answer 1

残念ながらアルゴリズム的な問題ではなくPython自体の遅さの問題のようです。
numpyのような高速なライブラリを使うか、地道に定数倍の改善を続けるしかありません。
とりあえず二重配列をやめれば大きく改善するはずです(ssを逆順に更新していけば二重配列は不要)。

Comments

[shake9]

ありがとうございます、細部の見直しを繰り返した結果無事ACできました。