Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/28

TopCoder Open 2010 Algorithm Qualification Round 3

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10929&rd=14278

問題

横 W 縦 H の芝生をダイアモンドカッターが切っていく.カッターの初期位置と,移動方向のプログラムが与えられたときに,芝生が何分割されているかを答える.

アプローチ

ある位置の芝生の左が切れているかどうかのフラグと上が切れているかどうかのフラグを用意しておき,プログラムを走らせて切っていき,最後に領域を数える.

領域を数えるのは再帰(スタック,深さ優先)だと最悪 10^6 になるのでオーバーフローする.queue を使って幅優先探索を行う.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#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 Rep(i,n)      for(int i=0;i<(n);++i)

bool cutu[1024][1024];
bool cutl[1024][1024];
bool glass[1024][1024];

queue<PII> q;

int pieces(int W, int H, int startx, int starty, vector <string> program)
{
	Rep(j,H+1) Rep(i,W+1)
		cutu[j][i] = cutl[j][i] = glass[j][i] = false;
	Rep(i,W+1)
		cutu[0][i] = cutu[H][i] = true;
	Rep(j,H+1)
		cutl[j][0] = cutl[j][W] = true;
	
	int x = startx;
	int y = starty;
	
	Rep(pp,sz(program)) Rep(p,sz(program[pp]))
	{
		switch(program[pp][p])
		{
		case 'U':
			cutl[--y][x] = true;
			break;
		case 'D':
			cutl[y++][x] = true;
			break;
		case 'L':
			cutu[y][--x] = true;
			break;
		case 'R':
			cutu[y][x++] = true;
			break;
		}
	}
	
	int c = 0;
	Rep(j,H) Rep(i,W) if(!glass[j][i])
	{
		c++;
		q.push(mp(i,j));
		while(!q.empty())
		{
			PII co = q.front(); q.pop();
			int x = co.first;
			int y = co.second;
			if(glass[y][x])
				continue;
			glass[y][x] = true;
			if(!cutu[y][x])   q.push(mp(x,y-1));
			if(!cutu[y+1][x]) q.push(mp(x,y+1));
			if(!cutl[y][x])   q.push(mp(x-1,y));
			if(!cutl[y][x+1]) q.push(mp(x+1,y));
		}
	}
	
	return c;
}

DiegoDiego2012/07/10 00:56The pucrahses I make are entirely based on these articles.

rcomsiercomsie2012/07/10 15:55WkGRgf <a href="http://ndjqpxpaabuy.com/">ndjqpxpaabuy</a>

lurhlpgihxdlurhlpgihxd2012/07/10 21:512sAKJD , [url=http://wyqyxabtrpox.com/]wyqyxabtrpox[/url], [link=http://fetlavsdhbsq.com/]fetlavsdhbsq[/link], http://frjyegfwmtje.com/

sxyqsmsxyqsm2012/07/12 12:11UCCj2u <a href="http://srlypizeryby.com/">srlypizeryby</a>

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

2010/03/23

SRM 464 ColorfulMazeTwo

| 07:02

http://www.topcoder.com/stat?c=problem_statement&pm=10742&rd=14149

Test Case #5 の小数点誤差が潰せなくて Test Case に手元で Fail する罠にひたすらはまり続けたけど,実はどうしようもなくて,TopCoder 側の Test では通ると気づいた...

http://gyazo.com/5a57c1f2ace67f70d3b7c35a7c1587ad.png

初めは幅優先探索で各マスの最大値を求めていく方法をとって枝刈りをしていたけど,これではダメなケースが発生する.というかこういう勘違いをしてしまったのは「同じ色のマスは一度踏んだらもう罠が発生しない」という設定が馴染みにくかったからだろう(しかも明文化されていない).

というわけでどの色の罠を踏んだかを覚えるだけで良いので,unsigned int colors 等に bit を立てて記録することにする.

確率は最後に計算すればいいけど枝刈りにも使うし最大値の更新を一緒にできるので prob として探索中に保持することにする.

探索ノードは Explore というクラスを作って,(x,y)座標と colors と prob を記録する.stack を使って深さ優先探索を行う.

これだけだと System Test の大きいケースで TLE してしまうので枝刈りが必要になる.

枝刈りの方法は

  1. 現時点での確率が,既に求まったゴールでの確率より低ければ探索中止
  2. あるマスに到達した際に,現状と同じまたは現状踏んでいる色のサブセットの色しか踏んでいない探索が既に行われているなら探索中止

という2通りがある.

2番目のものについて詳しく説明すると,色 {A, B} を踏んだ探索 S がマス X に到達した後に,色 {A, B, C} を踏んだ探索 T が同じマス X に到達したとすると,X から T の探索を続けても既に C を踏んでいる分 S より確率が高くなることは絶対に無いのでその時点で探索が終了できるということである.

この枝刈りは既に通ったマスには戻らないという枝刈りにもなっているので,探索がどのマスをたどってきたかを記録する必要がなくなる.これにより非常に高速に探索ができる.

各マスにどの罠を踏んで探索に訪れたかを vector<unsigned int> colors_map[50][50]; で記録しておき,枝刈りでは (colors_map[i][j][k]|colors)==colors で包含関係を調べている.ちなみに colors_map[i][j][k]|colors==colors にして小一時間はまった.

めでたく System Test を Passed.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

class Explore
{
public:
	int x;
	int y;
	unsigned int c;
	double p;
	Explore(int x_, int y_, unsigned int c_, double p_)
	:	x(x_),y(y_),c(c_),p(p_)
	{};
};

class ColorfulMazeTwo
{
public:

double getProbability(vector <string> maze, vector <int> trap)
{
	int h = int(maze.size());
	int w = int(maze[0].length());
	int ent_x=0, ent_y=0, exit_x=0, exit_y=0;
	
	for(int y=0; y<h;y++)
	{
		for(int x=0;x<w;x++)
		{
			if(maze[y][x]=='$')
			{
				ent_x = x;
				ent_y = y;
			}
			else if(maze[y][x]=='!')
			{
				exit_x = x;
				exit_y = y;
			}
		}
	}
	
	double max_prob = 0.0;
	
	Explore start(ent_x, ent_y, 0, 1.0);
	
	stack<Explore> s;
	s.push(start);
	
	vector<unsigned int> colors_map[50][50];
	
	while(!s.empty())
	{
		Explore e = s.top(); s.pop();
		for(int d=0;d<4;d++)
		{
			int i = e.x + dx[d];
			int j = e.y + dy[d];
			if(i<0 || i>=w || j<0 || j>=h)
			{
				continue;
			}
			char cell = maze[j][i];
			unsigned int colors = e.c;
			double prob = e.p;
			switch(cell)
			{
			case '#': // wall
				continue;
			case '$': // entrance
				continue;
			case '!': // exit
				max_prob = max(max_prob,e.p);
				continue;
			case '.': // empty cell
				break;
			default: // colored empty cell
				if(!(colors&(1u<<(cell-'A'))))
				{
					prob *= (100.0-trap[cell-'A'])/100.0;
				}
				colors |= (1u<<(cell-'A'));
				break;
			}
			// 枝刈り1
			if(prob<max_prob)
			{
				continue;
			}
			// 枝刈り2
			bool f = false;
			for(int k=0; k<int(colors_map[i][j].size()); k++)
			{
				// 現状のcolorsと同じまたはサブセットの色で既に探索が行われているか
				if((colors_map[i][j][k]|colors)==colors)
				{
					f = true;
					break;
				}
			}
			if(f)
			{
				continue;
			}
			
			colors_map[i][j].push_back(colors);
			Explore n(i,j,colors,prob);
			s.push(n);
		}
	}
	
	return max_prob;
}

};

StarlyStarly2011/07/24 01:22Well macadaima nuts, how about that.

ydruugerydruuger2011/07/24 19:13lIZcNk <a href="http://zuzttphaoahm.com/">zuzttphaoahm</a>

fxgpvlsvuqfxgpvlsvuq2011/07/24 23:10ULA6RD , [url=http://fkahebqribpy.com/]fkahebqribpy[/url], [link=http://spjuxhkvlvcp.com/]spjuxhkvlvcp[/link], http://yejgoezobwms.com/

qkghkxulqkghkxul2011/07/26 19:33IbIhPb <a href="http://cliwnrqqopng.com/">cliwnrqqopng</a>

sydckcjdsydckcjd2011/07/26 23:12h7gq0v , [url=http://ridkusaofvec.com/]ridkusaofvec[/url], [link=http://arnpkhbhkusx.com/]arnpkhbhkusx[/link], http://kxvpgeueaxbb.com/