AOJ2199 Differential Pulse Code Modulation

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

動的計画法

はじめに

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

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

問題

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

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

方針

n番目までの二乗和について、yn=kとして二乗和の最小値をdp[n][k]に記録していきます。

コード

残念ながらPythonではこの問題は、本質的ではない定数倍の工夫をしないとTLEとなります。

こちらのコードを参考にさせていただきました。

以下の工夫は高速化に役立ちました。

  • 全体を関数化する
  • minを用いずに比較と代入で実装する
  • dp[n][k]でhなくdp[k]を二つ用意する
  • dpnk = dp1[k]のような事前のメモ
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
def solve():
ans = []
INF = 10**10
while(1):
N, M = map(int,input().split())
if N==0:
break
C = [int(input()) for _ in range(M)]
X = [int(input()) for _ in range(N)]
dp1 = [INF]*256
dp2 = [INF]*256
dp1[128] = 0
cost = []
decoder = tuple(tuple(255 if i + c > 255 else 0 if i + c < 0 else i + c for c in C) for i in range(256))
ls_square = tuple(tuple((x - t)**2 for x in range(256)) for t in range(256))
for n in range(N):
x = X[n]
square = ls_square[x]
for k in range(256):
dpnk = dp1[k]
for code in decoder[k]:
# #dp[n+1][d] = min(dp[n+1][d], dp[n][k] + (d-X[n])**2)
new = dpnk + square[code]
if new < dp2[code]:
dp2[code] = new
dp1 = dp2[:]
dp2 = [INF]*256
ans.append(min(dp1))
for a in ans:
print(a)
solve()

記事情報

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