Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/24

Google Code Jam 2010 Round 1A B. Make it Smooth

| 16:01

http://code.google.com/codejam/contest/dashboard?c=544101#s=p1

解き方がわからなかった問題に再チャレンジ.

問題

最長 100 個の [0,255] の値(文字)が入った配列(文字列)が与えられる.隣り合う要素の差が M 以内であればこの文字列は smooth であるという.文字列に対して削除,置換,挿入の3操作が可能である.削除のコストは D で与えられ,置換のコストは置換前後の数値の差で定義される.挿入のコストは1要素につき I で与えられる.

このとき与えられた文字列を smooth にするために必要なコストの最小値を求める.

アプローチ

与えられた文字列に対してレーベンシュタイン距離の最小となるような文字列を作る操作を求める問題と等価である.

当たり前だけど,各文字を適当に固定して分岐して行く方法だと 255^100 以上の計算量になる.

と考えて実はこれやっぱりまさに典型的に DP で解けるのではないかと気付く.

(100 文字 + 頭 1)×(255 値)の配列 dp[101][256] を用意して,コストを代入して行く. dp[i][j] には i-1 番目の文字が j で i 番目の文字を決める直前のコストを代入する.

dp[0][j] は 0 で,他は十分大きな値にする(*1).INT_MAX を使ってしまうとコストを足したときに簡単に integer overflow を起こすので適度に大きくする.

前の文字 v[i-1] が j に決まったときに v[i] をある値 k に決めるコストを求めていき,k に決めた操作の中でコストが一番小さいものを取る.

これを繰り返して最後に N 文字目のコストで一番小さいものをとる(*2).

削除

v[i] を削除したときの累積コストは dp[i][j]+D である(*3).

変更

v[i] を文字 k に変更したときの累積コストは dp[i][j]+abs(v[i]-k) である(*4).ただし変更は M 以内に収まるような場合のみを行う.

挿入

j → k をつなぐ挿入を行うコストは I*((abs(k-j)-1)/M+1) である.

ここで気をつけなくてはいけないのが,v[i] の前,つまり v[i-1]=j → v[i]=k について挿入操作を行うのではなく,v[i] の後に行うということである.v[i]=j の後に,最後の文字が k になるように挿入を行うと, v[i+1] はあたかも v[i]=k に見える.

ポイントはこの挿入の操作は削除,変更を行ってコストを決めた後の v[i] に対して行うということである.

これを考慮しないと,値の変更・削除を行ってからその間に挿入を行う方がコストが安いケースに対応出来ない.

ここでハマった.

なので累積コストは dp[i][j]+I*((abs(k-j)-1)/M+1) ではなく dp[i+1][j]+I*((abs(k-j)-1)/M+1) とし,削除と挿入の後にコストの改善を行わなくてはならない.

ソースコード

以上のことをまとめるとこういうコードになる.

  • 挿入のところの if(k!=j) が必要ないので削除(2010/05/27 10:07)
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> VI;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define MN(a,b) a = min(a,b)

// 128 >= 100 chars + 1
// 256 = (0..255)
int dp[128][256];

int solve(int D, int I, int M, int N, VI &v)
{
	// initialization (*1)
	Rep(i,N+1) Rep(j,256) dp[i][j] = 10000000;
	Rep(j,256) dp[0][j] = 0;
	
	Rep(i,N)
	{
		//delete v[i] (*3)
		Rep(j,256)
			MN(dp[i+1][j], dp[i][j]+D);

		// modify v[i]=j to k (*4)
		Rep(j,256)
			Rep(k,256)
				if(abs(j-k)<=M)
					MN(dp[i+1][k], dp[i][j]+abs(v[i]-k));

		// insert chars after v[i] = j
		// the last inserted char is k (*5)
		if(M>0)
			Rep(j,256)
				Rep(k,256)
					MN(dp[i+1][k], dp[i+1][j]+I*((abs(j-k)-1)/M+1));
	}
	
	// (*2)
	int r = INT_MAX;
	Rep(j,256)
		MN(r,dp[N][j]);
	
	return r;
}

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int D, I, M, N;
		cin >> D >> I >> M >> N;
		VI v(N);
		Rep(n,N)
			cin >> v[n];
		int r = solve(D, I, M, N, v);
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

忍者最終号忍者最終号2010/05/24 14:291を数えないようにした方がもっと早くなりそうだ.

yuyarinyuyarin2010/05/27 10:16あ,本当ですね.
そのようにしてみました.