tozangezan's diary

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

Codeforces Round #286 (Div. 1)

Codeforces

久しぶりにコンテスト参加。問題は各地でたくさん解いているんだけど。

D:
平方分割的あれやるだけ。何も考えないし何でDなんだ。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int p[110000];
int q[110000];
int r[110000];
int UF[402][101000];
int FIND(int a,int b){
	if(UF[a][b]<0)return b;
	return UF[a][b]=FIND(a,UF[a][b]);
}
void UNION(int a,int b,int c){
	b=FIND(a,b);
	c=FIND(a,c);
	if(b==c)return ;
	UF[a][b]+=UF[a][c];
	UF[a][c]=b;
}
int sz[110000];
int conv[110000];
vector<int>sho[110000];
int tuf[520];
pair<int,int> sm[8000000];
int S;
int Find(int a){
	if(tuf[a]<0)return a;
	return tuf[a]=Find(tuf[a]);
}
void Union(int a,int b){
	a=Find(a);b=Find(b);if(a==b)return ;
	tuf[a]+=tuf[b];tuf[b]=a;
}
int cj[600];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d%d%d",p+i,q+i,r+i);
		p[i]--;q[i]--;r[i]--;
		sz[r[i]]++;
	}
	for(int i=0;i<402;i++)for(int j=0;j<101000;j++)UF[i][j]=-1;
	int ind=0;
	for(int i=0;i<b;i++)conv[i]=-1;
	for(int i=0;i<b;i++){
		if(sz[i]>=250){
			conv[i]=ind++;
		}
	}
	for(int i=0;i<b;i++){
		if(~conv[r[i]])UNION(conv[r[i]],p[i],q[i]);
		else sho[r[i]].push_back(i);
	}
	
	for(int i=0;i<b;i++){
		if(!sho[i].size())continue;
	//	printf("%d %d\n",i,(int)sho[i].size());
		for(int j=0;j<510;j++)tuf[j]=-1;
		map<int,int> M;
		int at=0;
		for(int j=0;j<sho[i].size();j++){
		//	printf("%d\n",sho[i][j]);
			int L,R;
			if(!M.count(p[sho[i][j]])){
				L=at;
				cj[at]=p[sho[i][j]];
				M[p[sho[i][j]]]=at;
				at++;
			}else L=M[p[sho[i][j]]];
			if(!M.count(q[sho[i][j]])){
				R=at;
				cj[at]=q[sho[i][j]];
				M[q[sho[i][j]]]=at;
				at++;
			}else R=M[q[sho[i][j]]];
			//printf("%d %d\n",L,R);
			Union(L,R);
		}
		//printf("%d\n",i);
		for(int j=0;j<at;j++)for(int k=j+1;k<at;k++){
			if(Find(j)==Find(k))sm[S++]=(make_pair(min(cj[j],cj[k]),max(cj[j],cj[k])));
		}
		//printf("%d\n",i);
	}
	std::sort(sm,sm+S);
	int c;
	scanf("%d",&c);
	for(int i=0;i<c;i++){
		int s,t;
		scanf("%d%d",&s,&t);s--;t--;
		int ret=0;
		for(int j=0;j<ind;j++)if(FIND(j,s)==FIND(j,t))ret++;
		ret+=upper_bound(sm,sm+S,make_pair(min(s,t),max(s,t)))-lower_bound(sm,sm+S,make_pair(min(s,t),max(s,t)));
		printf("%d\n",ret);
	}
	
}

A:
DP(二つキーを持つが、片方の幅が狭い)
なんでこんなのがAなんだ。というかこういうのはCF独特感すらある。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[31000][610];
int val[31000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int T=b;
	for(int i=0;i<a;i++){
		int p;scanf("%d",&p);
		val[p]++;
	}
	for(int i=0;i<31000;i++)for(int j=0;j<610;j++)dp[i][j]=-999999999;
	dp[b][300]=val[b];
	for(int i=b;i<30000;i++){
		for(int j=0;j<610;j++){
			if(dp[i][j]<0)continue;
			int sp=T+j-300;
			if(j&&sp>1&&i+sp-1<=30000)dp[i+sp-1][j-1]=max(dp[i+sp-1][j-1],dp[i][j]+val[i+sp-1]);
			if(i+sp<=30000)dp[i+sp][j]=max(dp[i+sp][j],dp[i][j]+val[i+sp]);
			if(j<609&&i+sp+1<=30000)dp[i+sp+1][j+1]=max(dp[i+sp+1][j+1],dp[i][j]+val[i+sp+1]);
		}
	}
	int ret=0;
	for(int i=0;i<31000;i++)for(int j=0;j<610;j++)ret=max(ret,dp[i][j]);
	printf("%d\n",ret);
}

B:
グラフの変なの。
連結成分ごとに、頂点数をnとするとそのなかに閉路があればn、そうでなければn-1を足していく。
グラフ理論ガチゲーは苦手だからちょっと強めに感じる。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[110000];
vector<int>rev[110000];
int v[110000];
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 num;
int con[110000];
void dfs(int a){
	v[a]=-2;
	for(int i=0;i<g[a].size();i++){
		if(!~v[g[a][i]]){
			dfs(g[a][i]);
		}
	}
	con[num]=a;
	v[a]=num++;
}
int hr[110000];
int cnt;
void dfs2(int a){
	v[a]=1;
	cnt++;
	for(int i=0;i<rev[a].size();i++){
		if(!~v[rev[a][i]]){
			dfs2(rev[a][i]);
		}
	}
}
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<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		rev[q].push_back(p);
		UNION(p,q);
	}
	for(int i=0;i<a;i++){
		v[i]=-1;
	}
	for(int i=0;i<a;i++){
		if(!~v[i]){
			dfs(i);
		}
	}
	int ssc=0;
	for(int i=0;i<a;i++)v[i]=-1;
	for(int i=a-1;i>=0;i--){
		if(!~v[con[i]]){
			cnt=0;
			dfs2(con[i]);
			if(cnt>1){
				hr[FIND(con[i])]=1;
			}
		}
	}
	int ret=0;
	for(int i=0;i<a;i++){
		if(UF[i]<0){
			int sz=-UF[i];
			ret+=sz-1+hr[i];
		}
	}
	printf("%d\n",ret);
}

22nd
2279 -> 2388 (+109)

やっぱり出てちゃんと通せばレートは上がるんだなあ。
結局今回も簡単枠しか通せないのであった。壁を感じる。