Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

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/