Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/24

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あ,本当ですね.
そのようにしてみました.