tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Codeforces Round #250 (Div. 1)

Codeforces

もうCodeforcesには出ません、と2月くらいに言いましたが、WFが近くそんなこと言ってられなくなったので参加しました。

A:
辺を全部切ることと、辺を切るときには辺につながっているうち大きいほうをはずせばコストが小さくなるということを考えれば、コストの大きい頂点からはずすのは当たり前。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int c[1100];
int v[1100];
pair<int,int>cost[1100];
vector<int>g[1100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
		cost[i]=make_pair(-c[i],i);
	}
	for(int i=0;i<b;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	std::sort(cost,cost+a);
	int ret=0;
	for(int i=0;i<a;i++){
		int at=cost[i].second;
		v[at]=1;
		for(int j=0;j<g[at].size();j++){
			if(!v[g[at][j]])ret+=c[g[at][j]];
		}
	}
	printf("%d\n",ret);
}

B:
どう考えても辺の両端の最小値が大きい順にソートしてUnion-Findするときにunionで併合される組の数を計算してかけてわるだけ・・・

#include<stdio.h>
#include<algorithm>
using namespace std;
int UF[110000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);
	if(a==b)return;
	UF[a]+=UF[b];
	UF[b]=a;
}
int c[110000];
pair<int,pair<int,int> > e[110000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)UF[i]=-1;
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		e[i]=make_pair(-min(c[p],c[q]),make_pair(p,q));
	}
	std::sort(e,e+b);
	long long val=0;
	for(int i=0;i<b;i++){
		int p=e[i].second.first;
		int q=e[i].second.second;
		int r=-e[i].first;
		if(FIND(p)!=FIND(q)){
			int sp=-UF[FIND(p)];
			int sq=-UF[FIND(q)];
			val+=(long long)sp*sq*r;
			UNION(p,q);
		}
	}
	printf("%.12f\n",(double)val/a/(a-1)*2);
}

C:
ICPC の 幾何力 (+申し訳程度の区間DP)
3点が同一直線上にあるのがめちゃくちゃ厄介。

#include<bits/stdc++.h>
using namespace std;
//ライブラリ さんがログアウトしました。
double x[210];
double y[210];
int ok[210][210];
Pt poly[210];
int dp[210][210];
int mod=1000000007;
int calc(int a,int b){
	if(~dp[a][b])return dp[a][b];
	if(a+2==b){
		if(ok[a][b])return dp[a][b]=1;
		else return dp[a][b]=0;
	}
	if(a+1==b){
		return dp[a][b]=1;
	}
	int ret=0;
	for(int i=a+1;i<b;i++){
		if(ok[a][i]&&ok[i][b])ret=(ret+(long long)calc(a,i)*calc(i,b)%mod)%mod;
	}
	return dp[a][b]=ret;
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%lf%lf",x+i,y+i);
		poly[i]=Pt(x[i],y[i]);
	}
	for(int i=0;i<210;i++)
		for(int j=0;j<210;j++)
			dp[i][j]=-1;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(i==j)continue;
			bool OK=true;
			double mx=(x[i]+x[j])/2;
			double my=(y[i]+y[j])/2;
			if(sGP(a,poly,Pt(mx,my))==-1)OK=false;
			for(int k=0;k<a;k++){
				if(iLL(poly[k],poly[(k+1)%a],poly[i],poly[j])==-1){
					if((!(k==i&&(k+1)%a==j))&&(!(k==j&&(k+1)%a==i))&&iSP(poly[i],poly[j],poly[k])==0&&iSP(poly[i],poly[j],poly[(k+1)%a])==0){
			//		if(i+1==j)printf("%d %d %d\n",i,j,k);
						OK=false;
					}
				}
				else if(iSS(poly[k],poly[(k+1)%a],poly[i],poly[j])){

					Pt p=pLL(poly[k],poly[(k+1)%a],poly[i],poly[j]);
					if((p-poly[i]).abs()>EPS&&(p-poly[j]).abs()>EPS){
						
						OK=false;
					}
				}
			}
			if(OK)ok[i][j]=1;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
		//	printf("%d ",ok[i][j]);
		}
		//printf("\n");
	}
	printf("%d\n",calc(0,a-1));
}

全部通る。
90th

てかD通すべきでしたね…