AOJ2143 Adaptive Time Slicing Quantization

問題リンク Adaptive Time Slicing Quantization

• 概要

N個の[0.0, 1.0]の実数値列と整数M, Lが与えられる。
実数値列をM個の区間に分割する。ただしどの区間も最低2つ以上の要素を持たなければならない。更に、各区間毎に以下のようにして二乗誤差を計算する
・区間の最小値minと最大値maxを調べる
・区間の各要素aを
Qi = min + (i-1)*(max-min)/(2^L-1) : (1 <= i <= 2^L)
の内で最も近いものに量子化し、量子化された値と本来の数値との二乗誤差の総和をとる
実数値列をM個の区間に分割したとき、各区間の二乗誤差の総和の最小値を求めよ。
2 <= N <= 256
1 <= M <= M/2
1 <= L <= 8

• 解法

DPもといメモ化探索です。
dp[i][j]: 数列のi番目以降を使ってj個の区間を作った時の最小値
という表を埋めていきながら探索します。
dp[i][j]を埋めるために、区間を決めるループO(N)と、量子化する値を決めるループO(2^L)が必要になるので、計算量がざっとO(N^2*M*2^L)かかり大分危険です。量子化する値を2分探索を使って求めればO(2^L)がO(log 2^L)=O(L)になるのでO(N^2*M*L)程度に落とせます。これでTLE 16000msに対して14080msで通りました。ギリギリセーフです。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Adaptive Time Slicing Quantization
public class AOJ2143 {

	int n, M, L, INF = 1<<29;
	double res;
	double[] a;
	double[][] dp;
	
	double bs(double min, double max, double x){
		int l = 1, r = 1<<L;
		while(r-l>1){
			int m = (l+r)/2;
			double v = min+(m-1)*(max-min)/((1<<L)-1);
			if(v<x)l=m;
			else r=m;
		}
		double lv = min+(l-1)*(max-min)/((1<<L)-1), rv = min+(r-1)*(max-min)/((1<<L)-1);
		return Math.abs(x-lv)<Math.abs(x-rv)?lv:rv;
	}
	
	double get(int k, int m){
		if(n==k){
			return m==0?0:INF;
		}
		if(m<0)return INF;
		if(dp[k][m]!=-1)return dp[k][m];
		if(n<=k+1)return INF;
		double min = a[k], max = a[k], res = INF;
		for(int i=k+1;i<n;i++){
			min = Math.min(min, a[i]); max = Math.max(max, a[i]);
			if(n<i+1+2*(m-1))break;
			double e = 0;
			for(int j=k;j<=i;j++){
				double s = bs(min, max, a[j]);
				e += (s-a[j])*(s-a[j]);
			}
			res = Math.min(res, e+get(i+1, m-1));
		}
		return dp[k][m] = res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt(); M = sc.nextInt(); L = sc.nextInt();
			if((n|M|L)==0)break;
			a = new double[n];
			for(int i=0;i<n;i++)a[i]=sc.nextDouble();
			dp = new double[n][M+1];
			for(double[]d:dp)Arrays.fill(d, -1);
			System.out.printf("%.8f\n", get(0, M));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2143().run();
	}
}