AOJ1167 ポロック予想

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167&lang=ja

この問題は動的計画法を用いて解くことができます。

方針

重複ありのナップザック問題です。正四面体数を計算していきながら、動的計画法を行います。
Pythonだと時間が厳しいため、本質的ではない高速化が必要でした。

状況によるのかもしれませんが、今回の場合は組み込み関数のminを自前の実装に書き換える事で3倍程度速くなり、TLEを回避できました。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def main():
ans = []
N = 10**6
dp = [10**10]*(N+1)
dp_odd = [10**10]*(N+1)
dp[0] = 0
dp_odd[0] = 0

for i in range(1,10**3):
w = i*(i+1)*(i+2)//6
if N<=w:
break
for n in range(N-w):
# dp[n+w] = min(dp[n]+1,dp[n+w]) # TLE
new = dp[n] + 1
if new < dp[n+w]:
dp[n+w] = new
if w&1==1:
for n in range(N-w):
#dp_odd[n+w] = min(dp_odd[n]+1,dp_odd[n+w]) # TLE
new = dp_odd[n] + 1
if new < dp_odd[n+w]:
dp_odd[n+w] = new

while(1):
S = int(input())
if S==0:break
ans.append([dp[S],dp_odd[S]])
for a,b in ans:
print(a,b)
if __name__ == '__main__':
main()

記事情報

  • 投稿日:2020年6月13日
  • 最終更新日:2020年6月13日