2014-03-09

■ CF #127 div1 20:35

A: 糞問

B: サンタさんがチョコレートケーキを配る問題に似てる。簡単

C: 一筆書きなので奇点は0 or 2なので順にDPするだけ

ツイートする

■ SRM 540 Div1 Med 18:06

550ptsですが3次元累積和を正しく書いて0除算しないようにすれば誰でも解けます。

#line 2 "RandomColoring.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
// I'll become a member of  IOI 2014 Japan team.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i
double dp[51][51][51];
double rui[161][161][161];
int cont[51][51][51];
class RandomColoring
{
	public:
	double calc(int or2,int og,int ob,int dis)
	{
		if(dis<0) return 0.0;
		or2+=60;
		og+=60;
		ob+=60;
		//or-dis~or+dis
		//og-dis~og+dis
		//ob-dis~ob+dis
		double ret=rui[or2+dis][og+dis][ob+dis];
		ret-=rui[or2-dis-1][og+dis][ob+dis];
		ret-=rui[or2+dis][og-dis-1][ob+dis];
		ret-=rui[or2+dis][og+dis][ob-dis-1];
		ret+=rui[or2-dis-1][og-dis-1][ob-dis-1]*2.0;
		ret+=(rui[or2+dis][og-dis-1][ob-dis-1]-rui[or2-dis-1][og-dis-1][ob-dis-1]);
		ret+=(rui[or2-dis-1][og+dis][ob-dis-1]-rui[or2-dis-1][og-dis-1][ob-dis-1]);
		ret+=(rui[or2-dis-1][og-dis-1][ob+dis]-rui[or2-dis-1][og-dis-1][ob-dis-1]);
		return ret;
	}
	double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) 
	{
		dp[startR][startG][startB]=1.0;
		for(int r=0;rfor(int g=0;gfor(int b=0;bint xx=max(0,r-d2);
					int yy=max(0,g-d2);
					int zz=max(0,b-d2);
					int xx2=min(maxR-1,r+d2);
					int yy2=min(maxG-1,g+d2);
					int zz2=min(maxB-1,b+d2);
					int zen=max(0,(xx2-xx+1)*(yy2-yy+1)*(zz2-zz+1));
					xx=max(0,r-d1+1);
					yy=max(0,g-d1+1);
					zz=max(0,b-d1+1);
					xx2=min(maxR-1,r+d1-1);
					yy2=min(maxG-1,g+d1-1);
					zz2=min(maxB-1,b+d1-1);
					zen-=max(0,(xx2-xx+1)*(yy2-yy+1)*(zz2-zz+1));
					cont[r][g][b]=max(0,zen);
				}
			}
		}
		for(int i=60;i<=160;i++)
		{
			for(int j=60;j<=160;j++)
			{
				for(int k=60;k<=160;k++)
				{
					rui[i][j][k]=rui[i-1][j][k]+rui[i][j-1][k]+rui[i][j][k-1];
					rui[i][j][k]-=rui[i-1][j-1][k-1]*2.0;
					rui[i][j][k]-=(rui[i-1][j-1][k]-rui[i-1][j-1][k-1]);
					rui[i][j][k]-=(rui[i-1][j][k-1]-rui[i-1][j-1][k-1]);
					rui[i][j][k]-=(rui[i][j-1][k-1]-rui[i-1][j-1][k-1]);
					if(i<=110&&j<=110&&k<=110&&cont[i-60][j-60][k-60]) rui[i][j][k]+=dp[i-60][j-60][k-60]/cont[i-60][j-60][k-60];
				}
			}
		}
		for(int i=1;ifor(int r=0;rfor(int g=0;gfor(int b=0;b1);
					}
				}
			}
			for(int i2=60;i2<=160;i2++)
			{
				for(int j=60;j<=160;j++)
				{
					for(int k=60;k<=160;k++)
					{
						rui[i2][j][k]=rui[i2-1][j][k]+rui[i2][j-1][k]+rui[i2][j][k-1];
						rui[i2][j][k]-=rui[i2-1][j-1][k-1]*2.0;
						rui[i2][j][k]-=(rui[i2-1][j-1][k]-rui[i2-1][j-1][k-1]);
						rui[i2][j][k]-=(rui[i2-1][j][k-1]-rui[i2-1][j-1][k-1]);
						rui[i2][j][k]-=(rui[i2][j-1][k-1]-rui[i2-1][j-1][k-1]);
						if(i2<=110&&j<=110&&k<=110&&cont[i2-60][j-60][k-60])
						{
							rui[i2][j][k]+=dp[i2-60][j-60][k-60]/cont[i2-60][j-60][k-60];
						}
					}
				}
			}
		}
		
		double ret=0.0;
		for(int r=0;rfor(int g=0;gfor(int b=0;bif(abs(r-startR)>d2 || abs(g-startG)>d2 || abs(b-startB)>d2)  continue;
					if(abs(r-startR)continue;
					ret+=dp[r][g][b];
				}
			}
		}
		return 1.0-ret;
	}
};

ツイートする