2014-03-01

■ Codeforces #233 Div1 03:48

ぬわあああん疲れたもおおおんなんでUnratedなんだああああああえんだああああいやあああああ

(息を整える)

A:

いくつに分けるか決めるとやるだけ。200行を超えるのでコード省略

B:

良問。でも解法は

dp[i][j]=dp[i-1][j-1]*(i*j/n^2)+dp[i-1][j]*(i*(n-j)/n^2)+dp[i][j-1]*((n-i)*j/n^2)+dp[i][j]*((n-i)*(n-j)/n^2)

を変形するだけ。

double dp[2005][2005];
bool used[2005];
bool used2[2005];
int n,m;
double calc(int remx,int remy)
{
	if(remx+remy==0) return dp[remx][remy]=0.0;
	if(dp[remx][remy]) return dp[remx][remy];
	double &res=dp[remx][remy];
	res+=1.0;
	if(remx) res+=(double)remx*(n-remy)/(double)(n*n)*calc(remx-1,remy);
	if(remy) res+=(double)remy*(n-remx)/(double)(n*n)*calc(remx,remy-1);
	if(remx && remy) res+=(double)remx*remy/(double)(n*n)*calc(remx-1,remy-1);
	res*=(double)n*n/(double)(n*n-(n-remy)*(n-remx));
	return res;
}
int main()
{
	srand((unsigned int)time(NULL));
	scanf("%d %d",&n,&m);
	for(int i=0;iint x,y; scanf("%d%d",&x,&y);
		--x; --y;
		used[x]=used2[y]=true;
	}
	int cnt=count(used,used+n,0);
	int cnt2=count(used2,used2+n,0);
	printf("%.10f\n",calc(cnt,cnt2));
}

C,E: 人の解く問題ではありません

D:

良く分からなかったのでてきとうなぎにsqrt-decompositionしたらなぜか通った

#define lim 398
int n,m,q,o;
bool in[50005]={};
vector<int>edge[50005];
vector<int>rem[50005];
vector<int>bigf[50005];
int sum[50005];
bool big[50005];
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	scanf("%d",&o);
	for(int i=0;iint x; scanf("%d",&x);
		in[x]=true;
	}
	for(int i=0;iint x,y; scanf("%d%d",&x,&y);
		edge[x].pb(y);
		edge[y].pb(x);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(edge[i].size()>=lim)
		{
			big[i]=true;
			for(int j=0;jwhile(q--)
	{
		char qr;  scanf(" %c",&qr);
		if(qr=='O')
		{
			int ql; scanf("%d",&ql);
			in[ql]=true;
			if(!big[ql])
			{
				for(int i=0;ifor(int i=0;iif(big[rem[ql][i]]) sum[rem[ql][i]]--;
				}
			}
			else
			{
				for(int i=0;ifor(int i=0;iif(big[rem[ql][i]]) sum[rem[ql][i]]--;
				}
			}
		}
		else if(qr=='F')
		{
			int ql; scanf("%d",&ql);
			in[ql]=false;
			if(!big[ql])
			{
				for(int i=0;ifor(int i=0;iif(big[rem[ql][i]]) sum[rem[ql][i]]++;
				}
			}
			else
			{
				for(int i=0;ifor(int i=0;iif(big[rem[ql][i]]) sum[rem[ql][i]]++;
				}
			}
		}
		else if(qr=='A')
		{
			int u,v; scanf("%d%d",&u,&v);
			edge[u].pb(v);
			edge[v].pb(u);
			if(big[u])
			{
				bigf[v].pb(u);
				sum[u]+=in[v];
			}
			if(big[v])
			{
				bigf[u].pb(v);
				sum[v]+=in[u];
			}
		}
		else if(qr=='D')
		{
			int u,v; scanf("%d%d",&u,&v);
			rem[u].pb(v);
			rem[v].pb(u);
			if(big[u])
			{
				sum[u]-=in[v];
			}
			if(big[v])
			{
				sum[v]-=in[u];
			}
		}
		else
		{
			int ql; scanf("%d",&ql);
			if(big[ql]) printf("%d\n",sum[ql]);
			else
			{
				int res=0;
				for(int i=0;ifor(int i=0;i"%d\n",res);
			}
		}
	}
}

systest 通る

oo-o- 18位

Rating 1935->1935(+-0)

今回のUnratedはTCでRedCoderやIOIの日本代表になるのとつりあいをとるためってはっきりわかんだね。(強気)

ツイートする