TopCoder SRM275 Div2 500Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。

Haarウェーブレット変換というのは、1909年にHarrによって導入された最初のウェーブレット変換である。1次元の変換は整数列を次のように変換する。最初に数列を近接した値のペアに分ける。最初は先頭と2番目、次に3番目と4番目という具合である。次に、これらのペアの輪を計算し、新しい数列をつくる。そして、こんどはペアの差を計算(先の値-後の値)し、新しく作成した数列の後ろに追加する。数列の結果はlevel-1変換という。この変換では入力として要素数が偶数であることが要求される。level-2変換は、level-1変換で作成した数列の前半分に対して同様のことを行うものである。つまり後ろ半分は何も変化しない。これらの操作は要素数が2の累乗であればいつでも可能である。data[]という整数列とLという値が与えられたとき、level-LのHaar変換の結果を返すメソッドを作成せよ。

例えば、{1, 2, 3, 4}という数列に対してlevel-1変換は{3, 7, -1, -1}となる。1+2=3、3+4=7、1-2=-1、3-4=-1だからである。level-2変換は{10, -4, -1, -1}である。3+7=10、3-7=-4だからである。後半の-1、-1は変化しない。

私の解答はこちら。

public class Haar1D {

 public int[] transform(int[] data, int L) {
  int[] ret = new int[data.length];
  int[] tmp = new int[data.length];
  for( int i=0 ; i<data.length ; i++ ){
   ret[i] = tmp[i] = data[i];
  }
  for( int i=0 ; i<L ; i++ ){
   int n = data.length/(int)Math.pow(2,i+1); // level-iで変換対象となる要素数の半分
   for( int j=0 ; j<n ; j++ ){
    ret[j] = tmp[2*j]+tmp[2*j+1]; // 前半
   }
   for( int j=0 ; j<n ; j++ ){
    ret[j+n] = tmp[2*j]-tmp[2*j+1]; // 後半
   }
   for( int j=0 ; j<data.length ; j++ ){
    tmp[j] = ret[j]; // 更新
   }
  }
  return ret;
 }

}

得点は322.87/500。要素の破壊を伴うため、2つの配列を用意して解答している。level2の問題にしては簡単かと思います。