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/

2010/03/20

SRM 464 Div2

| 22:10

SRM 464 Div2 Room 55

7回目のチャレンジにして記録をここにまとめることに.

Coding Phase226.84
Challange Phase0.00
System Test0.00
Point Total226.84
Division Placed157
Old Rating1132
Pating Change+42
New Rating1174
ProblemProblem NameCoding TimeStatusPoints
250ptColorfulBoxesAndBalls0:09:15.711Passed System Test226.84
500ptColorfulStrings1:05:27.615Opend0
1000ptColorfulMazeTwo---Unopend0

250 pt. を速攻で潰せなかったのが残念.問題の英文を読むのと図を把握するのに手間取った.500 pt. は submit が 10 秒間に合わなかったが,あとで System Test にかけると fail したのでどっちみちダメだった.まだまだ修行が足りない.challenge phase は参加せず.

今回は全体的に難しかったみたいで rating は up.複雑な気分だ...

SRM 464 ColorfulBoxesAndBalls

| 21:40

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

Sample Case: passed

System Test: passed

赤のボールと青のボール,すべて同じ色の箱に収まった場合の得点 (a) と,できるだけ違う色の箱に入れた場合の得点 (b) を比較して大きい方を返せばいいだけなので,一行で書ける.

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

using namespace std;

class ColorfulBoxesAndBalls
{
public:

int getMaximum(int nR, int nB, int oR, int oB, int bC)
{
	int a = nB*oB+nR*oR;
	int b = (nR>nB) ? (2*nB*bC+(nR-nB)*oR) : (2*nR*bC+(nB-nR)*oB);
	return max(a, b);
}
};

SRM 464 ColorfulStrings

| 21:19

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

Sample Case: passed

System Test: passed

問題の条件から

  • 2桁以上の数字では0と1が入ってはいけない
  • 同じ数字は2回現れない

ということがわかるので 2<=n<=8 で考えればいいことがわかるので,ひとまず枝刈りをせずに 2,3,4,5,6,7,8,9 を辞書順で生成していき colorful かチェックする.結果的に枝刈りをしなくても実行速度は十分であった.

数字は整数の配列 num[] で各桁を表現する.

辞書順の生成は再帰を使う (rec()).ある数字が使われたかを ap[] で記録しておき,使われていない数字を小さい方から num[pos] に入れていく.pos を 1 増やして再帰する.長さが桁数に達したら colorful かチェックを行う (colorful()).

colorful のチェックではそれまでの数字の積を記録 (mr[]) しておけば,ループを1重減らすことができる.

積のデータベースには set を利用している.insert() は既に要素があったときに .second で false が返されるので,既に積が出現している=colorful ではない場合を挿入と同時に判定できる.

あんまりスマートなコードだとは思わないけど,理解はしやすいと思う.

上位のコードはもっとシンプルだけどまだ解読出来ていない...

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

using namespace std;
inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

class ColorfulStrings
{
public:

bool colorful(int n, int* num)
{
	// the results of mul
	int mr[] = {1,1,1,1,1,1,1,1,1,1,};
	
	set<int> m;
	
	for(int len=1; len<=n; ++len)
	{
		for(int idx=0; idx<=n-len; ++idx)
		{
			mr[idx] *= num[idx+len-1];
			if(!m.insert(mr[idx]).second)
				return false;
		}
	}
	
	return true;
}

bool rec(int n, int k, int* num, int* ap, int pos, int &cnt)
{
	if(pos==n)
	{
		if(colorful(n, num)) cnt++;
		if(cnt==k) return true;
		return false;
	}
	
	for(int i=2; i<10; ++i)
	{
		if(ap[i]) continue;
		num[pos] = i;
		ap[i] = 1;
		if(rec(n, k, num, ap, pos+1, cnt)) return true;
		ap[i] = 0;
	}
	return false;
}

string getKth(int n, int k)
{
	if(n>8) return "";
	if(n==1) return (k>10) ? "" : tos(k-1);
	
	string s = "";
	int num[8];
	int ap[] = {0,0,0,0,0,0,0,0,0,0};
	int cnt = 0;
	
	if(rec(n, k, num, ap, 0, cnt))
	{
		for(int i=0; i<n; ++i) s += num[i]+'0';
	}
	return s;
}
	
	
};

ElenaElena2013/02/17 05:39That addresses several of my concerns acutlaly.

sdxtpjsdxtpj2013/02/18 07:467hgOED , [url=http://vkhpudkqbafn.com/]vkhpudkqbafn[/url], [link=http://ibikxlgbdgkx.com/]ibikxlgbdgkx[/link], http://trdttgtbmydr.com/

beidpbknybeidpbkny2013/02/19 14:45wqJCeV <a href="http://pkzbvtmxkrzw.com/">pkzbvtmxkrzw</a>

hcaepwobinzhcaepwobinz2013/02/19 20:07MApC6d , [url=http://desrxojmthft.com/]desrxojmthft[/url], [link=http://qcvljhvzomoh.com/]qcvljhvzomoh[/link], http://socvhhjtbmkl.com/