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;
}

Google Code Jam 2010 Round 1C C. Making Chess Boards

| 11:40

「多分解けると思う」とか書いたので解いてみた.1時間かからなかったので B で試行錯誤せずにこっちを先に解けばよかったと思う.

問題

各マスが白か黒かで塗られた板が与えられるのでそこからチェスボード(市松模様の正方形)を切り出していく問題.切り取れるサイズが大きい順,次に上に位置する順,次に左に位置する順,で切り取っていき,切り取ることができたチェスボードのサイズと個数を求める.

結果

単純な実装をしたけど large input に対しても1秒以内で答えが出た.

アプローチ

列方向を(右向き正)を x, i 軸とする.行方向(下向き正)を y, j 軸とする.

とりあえず hex で渡されたデータを bool に変換する(*1).

以下,したのようなデータを例にする.

 01234567→ x, i
0□■■□■□■■
1■□■■□■■■
2□■■□■□□□
3□■■■□■□■
4■□□□■□■□
5■□■■□■□■
6□■■□■□■□
7■■□□■□□■
↓ y, j

答えは

4 1 (3,3)
3 1 (3,0)
2 3 (0,0), (0,3), (0,5)
1 27

まずあるマスが x, y 方向に,市松模様がこれまでいくつつづいているのかを調べる(*2).配列を mx, my とすると,こんなふうな結果になる.

mx[8][8]
[1][2][1][2][3][4][5][1]
[1][2][3][1][2][3][1][1]
[1][2][1][2][3][4][1][1]
[1][2][1][1][2][3][4][5]
[1][2][1][1][2][3][4][5]
[1][2][3][1][2][3][4][5]
[1][2][1][2][3][4][5][6]
[1][1][2][1][2][3][1][2]

my[8][8]
[1][1][1][1][1][1][1][1]
[2][2][1][2][2][2][1][1]
[3][3][1][3][3][3][2][2]
[1][1][1][4][4][4][1][3]
[2][2][2][5][5][5][2][4]
[1][1][3][6][6][6][3][5]
[2][2][1][7][7][7][4][6]
[3][1][2][1][1][1][5][7]

大きい順に求めるので最大のサイズ,つまりボードの短い辺のサイズから見て行く(*3).この例の場合 8 だが,切り取れるチェスボードのサイズは 4 なので s=4 とする.

あるマス (i, j) に着目したときにそれがサイズ s のチェスボードになっているか判定する.上・左から切り取るので左上から見ていくようにループを回す.(i, j) = (3, 3) を例とする.

(i, j) から y 方向にサイズ s だけ市松模様になっている条件は

my[j+s-1][i] - my[j][i] == s-1

である.市松模様が続いていれば my の値は 1 ずつ増えていくので最初のマス (i,j) と最後のマス (i, j+s-1) の my の差が s-1 になっていなければならない.逆に s-1 より小さい場合は途中で市松模様が切れていることがわかる(*4).

my[8][8]
 1  1  1  1  1  1  1  1 
 2  2  1  2  2  2  1  1 
 3  3  1  3  3  3  2  2 
 1  1  1 (4) 4  4  1  3 
 2  2  2  5  5  5  2  4 
 1  1  3  6  6  6  3  5 
 2  2  1 [7] 7  7  4  6 
 3  1  2  1  1  1  5  7

この例では (3, 3) は (4),(3, 3+s-1) = (3, 6) は [7] であるので条件を満たす.(3, 7) は 1 なので市松模様が切れていることが分かる.なので (3, 3) からサイズ 5 のチェスボードは切り取れない.

次に [j,j+s-1] のそれぞれの行について x 方向に市松模様が続いているか見て行く(*5).すべての行について同様の条件が成り立てば,チェスボードになっていると判定できる(*6).

mx[8][8]
 1  2  1  2  3  4  5  1 
 1  2  3  1  2  3  1  1 
 1  2  1  2  3  4  1  1 
 1  2  1 (1) 2  3 [4] 5 : j   = 3
 1  2  1 (1) 2  3 [4] 5 : j+1 = 4
 1  2  3 (1) 2  3 [4] 5 : j+2 = 5
 1  2  1 (2) 3  4 [5] 6 : j+s-1 = 6 (s=4)
 1  1  2  1  2  3  1  2

例では (3, j)→(6,j) (j∈[3,6]) のそれぞれについて差が s-1 = 3 になっているので市松模様になっている.

[i,i+s-1] のそれぞれの列について y 方向に市松模様が続いているのか調べる必要はない.これで十分である.

切り取った部分は 0 を代入して切り取ったことを示しておく(*7).

mx[8][8]
 1  2  1  2  3  4  5  1 
 1  2  3  1  2  3  1  1 
 1  2  1  2  3  4  1  1 
 1  2  1  0  0  0  0  5 
 1  2  1  0  0  0  0  5 
 1  2  3  0  0  0  0  5 
 1  2  1  0  0  0  0  6 
 1  1  2  1  2  3  1  2

これの操作をサイズについて大きい順で,上から,左から,行っていけば良い.

ソースコード

  • 初期化が冗長だったので冗長部分を削除
    • mx[], my[] には初めから 1 を代入すればいい
    • b[][] は false で初期化しなくてもいい
  • 切り取った箇所に代入する値を -1 から 0 に変更
  • 高速化のためサイズ 1 のボードの数を数えるのをやめて,計算する方法に変更
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define ForD(i,a,b)   for(int i=(a);i>(b);--i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

#define sz(a) int((a).size())

bool b[512][512]; // 各マスの色, false なら白
int mx[512][512]; // x 方向に何マス市松が続いているか
int my[512][512]; // y 方向に何マス市松が続いているか
// mx, my は切り取られたら 0 を代入

int solve(int M, int N, VS &v)
{
	// 初期化
	Rep(j,512) Rep(i,512)
		mx[j][i] = my[j][i] = 1;
	
	// 入力が Hex で渡されるので 2 値に変換 (*1)
	Rep(j,M) Rep(i,N/4) ForD(k,3,-1)
	{
		char c = (v[j][i]>='A')?v[j][i]-'A'+10:v[j][i]-'0';
		b[j][i*4+3-k] = (((c>>k)&1u)==1u);
	}
	
	// x 方向に市松模様が続く数を数える (*2)
	Rep(j,M) For(i,1,N) if(b[j][i]!=b[j][i-1])
		mx[j][i] = mx[j][i-1]+1;
	
	// y 方向に市松模様が続く数を数える
	Rep(i,N) For(j,1,M) if(b[j][i]!=b[j-1][i])
		my[j][i] = my[j-1][i]+1;
	
	int ms = min(N,M); // 切り出せる最大のサイズ
	VI scv(ms);        // サイズごとの切り出した個数
	
	int cut = 0;
	
	// サイズの大きい順に (*3)
	ForD(s,ms,0)
	{
		scv[ms-s] = 0;
		// あるマス (i,j) に着目
		Rep(j,M) Rep(i,N)
		{
			// 既に切り取られた
			if(mx[j][i]<0) continue;

			// 範囲オーバー
			if(i+s-1>=N) continue;
			if(j+s-1>=M) continue;

			// y 方向に市松模様が続かない (*4)
			if(my[j+s-1][i]-my[j][i]<s-1) continue;

			// 各行について x 方向に市松模様が続くか (*5)
			bool f = true;
			For(y,0,s) if(mx[j+y][i+s-1]-mx[j+y][i]!=s-1)
			{
				f = false;
				break;
			}
			// チェスボードになった (*6)
			if(f)
			{
				scv[ms-s]++;
				cut += s*s;
				// 切り取る (*7)
				For(y,j,j+s) For(x,i,i+s)
					mx[y][x] = my[y][x] = -1;
			}
		}
	}

	scv[0] = M*N - cut;
	
	// 数えて出力
	int c = 0;
	Rep(i,ms) if(scv[i]>0)
		c++;
	cout << c << endl;
	
	ForD(s,ms,0) if(scv[ms-s]>0)
		cout << s << " "<<scv[ms-s]<<endl;
	
	return 0;
}

int main(int argc, char* argv[])
{
	int num_of_test_cases;
	cin >> num_of_test_cases;
	
	Rep(test_case,num_of_test_cases)
	{
		int M, N;
		cin >> M >> N;
		VS v(M);
		Rep(i,M) cin >> v[i];
		cout << "Case #" << test_case+1 << ": ";
		solve(M, N, v);
	}
	
	return 0;
}

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

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