AOJ 2199: 差分パルス符号変調 (Differential Pulse Code Modulation)

はじめに

• 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199
• ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1362790
• Javaで実装
• すごく良い問題だと思います

方針

問題文にあるように、貪欲法では解けないので、探索をすることになる。 しかし、全探索すると最悪で16²⁰⁰⁰となってしまい間に合わない。

そこで動的計画法を使う。この問題においては、「今何番目か」「今の値はいくらか」という状態のなかで「最小二乗誤差の和」を最小にすればいい。つまり、dp[20000][256] サイズのテーブルを埋めていく処理になるが、実際、dp[i+1]の値を更新するにはdp[i]の値しか必要にならないため、テーブルのサイズはsp[2][256]で十分である。これを行わないとmemory limitを超えてしまう。

計算量は、悪く見積もって N * 256 * M ＜ 8.2 * 10⁷ である。最初の方は信号の値の選択肢が少ないため、もう少しオーダーは減り、また time limit が 8sec なのでなんとか通るようだ。

実装

class Main{
    static int inf = 1<<28;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String[] in = br.readLine().split(" ");
            int n = Integer.parseInt(in[0]);
            int m = Integer.parseInt(in[1]);
            if(n == 0 && m == 0) break;

            int[] c = new int[m];
            int[] x = new int[n];
            for (int i = 0; i < m; i++) {
                c[i] = Integer.parseInt(br.readLine());
            }
            for (int i = 0; i < n; i++) {
                x[i] = Integer.parseInt(br.readLine());
            }

            int[][] dp = new int[2][256];
            // dpテーブルの初期化
            for(int j = 0; j < 256; j++){
                dp[0][j] = inf;
                dp[1][j] = inf;
            }
            
            // 最初の状態
            dp[0][128] = 0;
            
            for(int i = 1; i <= n; i++){
                // DPテーブルの初期化
                for(int j = 0; j < 256; j++){
                        dp[i%2][j] = inf;
                }
                
                // 探索
                for(int j = 0; j < 256; j++){
                    int sum = dp[(i-1)%2][j];
                    if(sum == inf) continue;
                    for(int k = 0; k < m; k++){
                        // 次の値
                        int next_j = j + c[k];
                        next_j = Math.max(0, Math.min(255, next_j));
                        // 二乗誤差を足す
                        int next_sum = sum + sq(next_j - x[i-1]);
                        dp[i%2][next_j] = Math.min(dp[i%2][next_j], next_sum);
                    }
                }
            }
            
            int ans = inf;
            for(int i = 0; i < 256; i++){
                ans = Math.min(ans, dp[n%2][i]);
            }
            System.out.println(ans);
        }
    }

    public static int sq(int i) {
        return i * i;
    }

    public static double sq(double d) {
        return d * d;
    }
}