VKCup Round 1

700人くらい通過。400位。あぶないあぶない。

A:Greedyする問題
Greedyする。気づくのが遅かったので、Bといてからこっちといた。

#include<stdio.h>
#include<algorithm>
using namespace std;
int p[100000];
int q[100000];
pair<int,int>  ans[100000];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<b;i++)scanf("%d",q+i);
	int now=0;
	int ret=0;
	for(int i=0;i<a;i++){
		while(now<b&&q[now]<p[i]-c){
			now++;
		}
		if(now<b&&q[now]<=p[i]+d){
			ans[ret++]=make_pair(i,now);
			now++;
			
		}
	}
	printf("%d\n",ret);
	for(int i=0;i<ret;i++)printf("%d %d\n",ans[i].first+1,ans[i].second+1);
}

B:場合わけするだけの問題
場合分けする。

#include<stdio.h>
#include<algorithm>
using namespace std;
int cart[1000][1000];
int size[1000];
pair<int,int> p[1000];
pair<int,int> q[1000];
pair<int,int> s[1000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int P=0;
	int Q=0;
	for(int i=0;i<a;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		if(d==1)p[P++]=make_pair(c,i);
		if(d==2)q[Q++]=make_pair(c,i);
		s[i]=make_pair(c,d);
	}
	std::sort(p,p+P);
	std::sort(q,q+Q);
	if(P>=b){
		for(int i=0;i<b;i++){
			cart[i][size[i]++]=p[i+P-b].second;
		}
		for(int i=b;i<P;i++){
			cart[0][size[0]++]=p[P-1-i].second;
		}
		for(int i=0;i<Q;i++){
			cart[0][size[0]++]=q[i].second;
		}
	}else{
		for(int i=0;i<P;i++)cart[i][size[i]++]=p[i].second;
		for(int i=P;i<b;i++){
			cart[i][size[i]++]=q[i-P].second;
		}
		for(int i=b-P;i<Q;i++){
			cart[b-1][size[b-1]++]=q[i].second;
		}
	}
	double ret=0;
	for(int i=0;i<b;i++){
		int M=1999999999;
		double val=0;
		for(int j=0;j<size[i];j++){
			val+=s[cart[i][j]].first;
			M=min(M,s[cart[i][j]].first);
		}
		if(s[cart[i][0]].second==1)val-=(double)M/2.0;
		ret+=val;
	}
	printf("%.1f\n",ret);
	for(int i=0;i<b;i++){
		printf("%d",size[i]);
		for(int j=0;j<size[i];j++)printf(" %d",cart[i][j]+1);
		printf("\n");
	}
}

D:木DPするだけの問題
木DPする。ちなみにPKUからTreeのソースをコピペしてすこし変えるというのもある。なかなかデバッグに苦労した(入力の2つにpush_backすることと、部分木がほげ〜のところで奇数通りになることがあるのですぐに割ってはいけないこと)

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> G[50000];
vector<int>g[50000];
int dp[50000][501];
int n,k;
void dfs(int a,int b){
	for(int i=0;i<G[a].size();i++){
		if(b!=G[a][i]){
			g[a].push_back(G[a][i]);
			dfs(G[a][i],a);
		}
	}
}
long long ret=0;
void solve(int a){
	for(int i=0;i<g[a].size();i++)solve(g[a][i]);
	for(int i=0;i<g[a].size();i++){
		for(int j=0;j<k;j++){
			dp[a][j+1]+=dp[g[a][i]][j];
		}
	}
	dp[a][0]=1;
	for(int i=1;i+i<=k;i++){
		long long S=0;
		long long T=0;
		long long now=0;
		for(int j=0;j<g[a].size();j++){
			S+=dp[g[a][j]][i-1];
			T+=dp[g[a][j]][k-i-1];
			now+=(long long)dp[g[a][j]][i-1]*dp[g[a][j]][k-i-1];
		}
	//	printf("%lld ",S*T-now);
		ret+=(S*T-now)/((i+i==k)?2:1);
	}
	ret+=dp[a][k];
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	n=a;
	k=b;
	for(int i=0;i<a-1;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		G[c-1].push_back(d-1);
		G[d-1].push_back(c-1);
	}
	dfs(0,-1);
	solve(0);
	printf("%lld\n",ret);
}

Result
全部通った。レートも120くらい上がってLucky.