Python in Excelに向けて改めてPythonの勉強をしようと思ったことと、AOJでPyPy3が使えるようになったのをたまたま知ったことから、以前ハマった問題を解いてみました。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199&lang=jp
- xの配列で与えられる量子化信号（0～255）を、そのままではなく差分を取る形で記録する
- 差分はx[i]-x[i-1]で取得するのではなく所与の配列c（コードブック）から選択する（xの1つごとに選び直せる）
- 復元後の信号には当然誤差が発生するが、誤差の二乗和が最小になるようcを選択していった場合の最小値はいくらか
なんとか通ったPyPy3でのAC例はこちら。Python3だと遅すぎて無理です。
while True:
n, m = map(int, input().split())
if n == m == 0:
break
else:
c = [int(input()) for i in range(m)]
x = [0]+[int(input()) for i in range(n)]
dp = [[10**9]*256 for i in range(n+1)]
dp[0][128] = 0
for i in range(n):
for j in range(256):
for k in c:
to = j+k
if to < 0:
to = 0
elif to > 255:
to = 255
dp[i+1][to] = min(dp[i][j]+(to-x[i+1])**2, dp[i+1][to])
print(min(dp[n])) ２次元dpをやるわけですが配列dpの軸の1つは0～n（xに対応）、もう1つは0～255（信号値が取りうる範囲）とします。
改めてやってみてもこの選択が思いつきませんでした;-o-)解説を見ればごもっともという気がするんですが、考えていると0～m（コードブックcに対応）を使うのではないかなどとセンスのない方向に行ってしまいます。
漸化式自体は難しくなく、cの各要素に対応する次の信号値を計算し、二乗和が小さくなるようなら置き換えるというだけです。ただし復元後の信号値が0未満になる場合は0に、255超になる場合は255に丸めるというのが曲者で、これにより
dp[i][j] = min(dp[i-1][from]～)
のように配列を後戻りする形で参照しようとすると面倒が増えるという罠があります。
最終的な答えは最後のxにおける二乗和の最小値つまりmin(dp[n])となります。
言語の恩恵でコードは割と短く済んでいるものの、実際は試行錯誤しているうちに何時間かかかってしまいました。
問題は学生向けプログラミングコンテストで出題されたものだそうですが、こんなものを30分とかで解ける人たちはやっぱり頭の作りが違うと思いました。
