ICPCのdpcmデコード問題解いた

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2199

問題解いた物を改造してコードを読みやすくして、標準エラーに最小二乗和、標準出力にデコードしたバイナリを吐くようにした
ここのファイルをデコードするとノイズの後、ゆっくりの声がきこえる
http://acm-icpc.aitea.net/index.php?2010%2FPractice%2F%CC%CF%B5%BC%B9%F1%C6%E2%CD%BD%C1%AA%2F%CC%E4%C2%EA%CA%B8%A4%C8%A5%C7%A1%BC%A5%BF%A5%BB%A5%C3%A5%C8

音量注意
./a.out < C1 > decodedata
cat decodedata > /dev/dsp

dpcm.h

class Decodedpcm
{
private:
  std::vector <std::vector<int> > cache;
  std::vector<int> sample;
  std::vector<int> codebook;
  int cook(int, int); //実際にメモ化再帰を行う所                                                                           

public:
  Decodedpcm(std::vector<int>,std::vector<int>); //暗号データとコードブックのvectorを引数にとる
  virtual ~Decodedpcm(){}
  int saisyojijyo(); //最小二乗和を返すためのエントリーポイント
  void printdecodedata(); //標準出力にバイナリでデコードデータを出す
};

dpcm.cc

#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include "dpcm.h"

using namespace std;
template<class T> inline T sqr(T x) {return x*x;}

//初期化リスト、二次元vectorをすべて-1で初期化して空の値を表現する、入力データの数ぶんだけ列を初期化する。
Decodedpcm::Decodedpcm(vector<int> insample, vector<int> incodebook)
  :cache(int(insample.size()) + 1, vector<int>(256, -1)),sample(insample),codebook(incodebook)
{}

//メモ化再帰、見ためをシンプルにするために128をコードブックぶんだけ足したものをエントリーポイントからもらわなければいけない->yの値
int Decodedpcm::cook(int sample_index, int y)
{
  //-1だったら空、キャッシュされてるならばキャッシュされてる値を返す
  //インデックスの値がvectorの範囲を超えていたらゼロを返す
  if(cache[sample_index][y] >= 0)
    {
      return cache[sample_index][y];
    }
  else if(sample_index == int(sample.size()))
    {
      return 0;
    }
  else
    {
      //その木で一番小さい葉までのコストの道を選ぶ
      int mincost = INT_MAX;
      for(vector<int>::iterator it = codebook.begin(); it != codebook.end(); ++it)
	{
	  int next_y = y + (*it);
	  if(next_y < 0){next_y = 0;}
	  else if(next_y > 255){next_y = 255;}

	  int cost = sqr<int>(sample.at(sample_index) - y);
	  int cooked = cost + cook((sample_index + 1), next_y);
	  //帰ってきた葉までのコストを更新する、小さいならば更新する
	  mincost = min(mincost, cooked);
	}
      //キャッシュして、一番小さいコストを返す
      return cache[sample_index][y] = mincost;
    }
}

//最小二乗和を返す、エントリーポイント、インデックス0の一番小さい二乗和を返す、コードブックの範囲のみで判断する
int Decodedpcm::saisyojijyo()
{
  int tmpmin = INT_MAX;
  for(vector<int>::iterator it = codebook.begin(); it != codebook.end(); ++it)
    {
      int next_y = 128 + (*it);
      if(next_y < 0){next_y = 0;}
      else if(next_y > 255){next_y = 255;}

      tmpmin = min(tmpmin, cook(0, next_y));
    }
  return tmpmin;
}
//http://ja.wikipedia.org/wiki/Sun%E3%82%AA%E3%83%BC%E3%83%87%E3%82%A3%E3%82%AA%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB
//デコードしたデータを標準出力(.auファイル)に出す、変形したエントリーポイント、違うのはサンプルの長さぶんだけ探索するのと、小さい二乗和を見つけた時、出力データも保持する所
void Decodedpcm::printdecodedata()
{
  unsigned char y = 128;

  for(int i = 0; i < int(sample.size()); ++i)
    {
      int samplemin = INT_MAX;
      int tmpy = 0;
      for(vector<int>::iterator it = codebook.begin(); it != codebook.end(); ++it)
	{
	  int x = y + (*it);
	  if(x < 0){x = 0;}
	  else if(x > 255){x = 255;}

	  if(samplemin > cook(i,x))
	    {
	      samplemin = cook(i,x);
	      tmpy = x;
	    }
	}
      y = tmpy;
      cout << y;
    }
}


//メインループを使う
//処理と出力をきりわける
//リソースの確保、リリース
int main()
{
  int codebooklen,samplelen;

  unsigned char header[4] = {0x2e,0x73,0x6e,0x64};//文字データで.snd
  unsigned char offset[4] = {0,0,0,24}; //ヘッダのサイズ
  unsigned char datasize[4] = {255,255,255,255}; //データサイズ、わからなかったら0xffffffでいいらしい
  unsigned char encoding[4] = {0,0,0,2};//リニアPCM形式
  unsigned char samplerate[4] = {0,0,31,64};//8khz
  unsigned char channel[4] = {0,0,0,1};//モノラルかステレオか何か
  
  for(int i = 0; i < 4; ++i) cout << header[i];
  for(int i = 0; i < 4; ++i) cout << offset[i];
  for(int i = 0; i < 4; ++i) cout << datasize[i];
  for(int i = 0; i < 4; ++i) cout << encoding[i];
  for(int i = 0; i < 4; ++i) cout << samplerate[i];
  for(int i = 0; i < 4; ++i) cout << channel[i];

  while(cin >> samplelen >> codebooklen)
    {
      if((samplelen == 0) && (codebooklen == 0)){break;}

      vector<int>sample, codebook;
      for(int i = 0; i < codebooklen; ++i)
	{
	  int x;
	  cin >> x;
	  codebook.push_back(x);
	}
  
      for(int i = 0; i < samplelen; ++i)
	{
	  int x;
	  cin >> x;
	  sample.push_back(x);
	}

      Decodedpcm *my_decoder = new Decodedpcm(sample, codebook);

      cerr << my_decoder->saisyojijyo() << endl;
      my_decoder->printdecodedata();
      delete my_decoder;
    }
  return 0;
}
//http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2199
//128からコードブックの値を選んで足し引きする
//足し引きするたび圧縮データ列の一つとひきざんして二乗する
//足し引きした値（最初なら128を）もちこしてまたコードブックを選んで次のサンプルと二乗する
//二乗した値を足し合わせて最小となるコードブックをえらんで、二乗した値を出力する

yppp’s diary

info

ICPCのdpcmデコード問題解いた