2013-12-17

■ USACO december contest (silver) 23:26

1問目

時間iまでに選んでる牛がi頭以下ならokなので

dp[i]=(i頭選ぶときの最大値)を使いまわす。

たぶんO(N*di_max)=O(10^8)くらい

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int dp[10005][2]={};
vector<int>best[10005];
int main(){
	int n;
	FILE* aa=fopen("msched.in","r");
	FILE* bb=fopen("msched.out","w");
	fscanf(aa,"%d",&n);
	int ret=0;
	int lim=0;
	for(int i=0;iint a,b;
		fscanf(aa,"%d %d",&a,&b);
		best[b].pb(a);
		lim=max(lim,b);
	}
	for(int i=1;i<10005;i++)
	{
		if(best[i].empty()) continue;
		sort(best[i].begin(),best[i].end());
		reverse(best[i].begin(),best[i].end());
		int cur=0;
		for(int j=0;jint last=0;
	int cur=0;
	int ne=1;
	for(int i=1;i<=lim;i++)
	{	
		if(best[i].empty()) continue;
		for(int ii=0;ii<10005;ii++)dp[ii][ne]=0;
		for(int j=last;j>=0;j--)
		{
			for(int k=min(i-j,(int)best[i].size());k>=0;k--)
			{
				int f=0;
				if(k) f=best[i][k-1];

				dp[j+k][ne]=max(dp[j+k][ne],dp[j][cur]+f);
			}
		}
		last=i;
		cur=1-cur;
		ne=1-ne;
	}
	//int ret=0;
	for(int i=0;i<=lim;i++) ret=max(ret,dp[i][cur]);
	fprintf(bb,"%d\n",ret);
	//cin >> ret;
	return 0;
}

2問目

配列を2種類に分けてwarshall-floydするだけ

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
long long d[205][205][2];
void warshall_floyd(int V){
	for(int k=0;kfor(int i=0;ifor(int j=0;j0]=min(d[i][j][0],d[i][k][0]+d[k][j][0]);
				d[i][j][1]=min(d[i][j][1],d[i][k][1]+d[k][j][0]);
				d[i][j][1]=min(d[i][j][1],d[i][k][1]+d[k][j][1]);
				d[i][j][1]=min(d[i][j][1],d[i][k][0]+d[k][j][1]);
			}
		}
	}
}

int main(){
	FILE* xx=fopen("vacation.in","r");
	FILE* yy=fopen("vacation.out","w");
	int n,m,k,q;
	fscanf(xx,"%d %d %d %d",&n,&m,&k,&q);
	for(int i=0;i<205;i++)for(int j=0;j<205;j++)for(int l=0;l<2;l++)
	{
		if(i!=j) d[i][j][l]=1000000000000LL;
		else if(i0]=1000000000000LL,d[i][j][1]=0;}
		else { d[i][j][0]=0,d[i][j][1]=1000000000000LL;}
	}

	for(int i=0;iint a,b,c;
		fscanf(xx,"%d %d %d",&a,&b,&c);
		if(a-111][b-1][1]=min(d[a-1][b-1][1],c*1LL);
		else d[a-1][b-1][0]=min(d[a-1][b-1][0],c*1LL);
	}
	warshall_floyd(n);
	int ret=0;
	long long val=0;
	for(int i=0;iint a,b;
		fscanf(xx,"%d %d",&a,&b);
		//printf("%lld\n",d[a-1][b-1][1]);
		if(d[a-1][b-1][1]<1000000000000LL)
		{
			ret++;
			val+=d[a-1][b-1][1];
		}
	}

	fprintf(yy,"%d\n%lld\n",ret,val);
	//cin >> ret;
}

3問目

今いる箇所からどれだけ進めば抜けられるかとサイクルを持っておくと

だいたいやるだけになる

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#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;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int r[100005];
int ne[100005];
int check[100005]={};
bool used[100005]={};
bool used2[100005]={};
int sd[100005];
bool in[100005]={};
vectorint>,map<int,int> > >root;
int belong[100005];
int idx=0;
int main(){
	FILE* xx=fopen("shuffle.in","r");
	FILE* yy=fopen("shuffle.out","w");
	int n,m,q;
	fscanf(xx,"%d %d %d",&n,&m,&q);
	for(int i=1;i<=m;i++)
	{
		fscanf(xx,"%d",&ne[i]);
		r[ne[i]]=i;
		in[ne[i]-1]=true;
	}
	
	for(int i=1;i<=m;i++)
	{
		if(used[i] || used2[i] || !in[i]) continue;
		int cur=i;
		int val=0;
		queue<int>returns;
		while(1)
		{
			returns.push(cur);
			if(cur==r[1])
			{
				used2[cur]=true;
				used[cur]=true;
				while(used[r[cur+1]]) { used2[r[cur+1]]=true; used[r[cur+1]]=false; cur=r[cur+1];}
				break;
			}
			else if(used[cur])
			{
			vector<int>vec;
			map<int,int>rev;
				while(!returns.empty())
				{
					check[returns.front()]=-INF;
					vec.pb(returns.front());
					rev[returns.front()]=vec.size()-1;
					belong[returns.front()]=idx;
					returns.pop();
				}
				vec.pop_back();
				root.pb(mp(vec,rev));
				idx++;
				break;
			}
			
			used[cur]=true;
			cur=ne[cur]-1;
			val++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(in[i]) continue;
		
		{
			queue<int>returns;
			int cur=i;
			int val=0;
			while(1)
			{
				returns.push(cur);
				if(cur==r[1]) break;
				cur=ne[cur]-1;
				val++;
			}
			vector<int>vec;
			map<int,int>rev;
			while(!returns.empty())
			{
				check[returns.front()]=(val--);
				vec.pb(returns.front());
				rev[returns.front()]=vec.size()-1;
				belong[returns.front()]=idx;
				returns.pop();
			}
			root.pb(mp(vec,rev));
			idx++;
			//break;
		}
	}
	for(int i=m+1;i<=n;i++)
	{
		int f=i-m;
		f+=check[m];
		if(f<0) check[i]=-INF;
		else check[i]=f;
	}
	for(int i=1;i<=m;i++)
	{
		if(check[i]!=-INF && check[i]<=n-m)
		{
			sd[check[i]+1]=i; //cout << i << " " << check[i]+1<< endl;
		}
		else
		{
			int d=belong[i];
			int id=(root[d].second)[i];
			id+=(n-m+1);

			id%=(root[d].first.size());
			sd[n-m+(root[d].first)[id]+1]=i; //cout << i << " " << n-m+(root[d].first)[id]+1<< endl;
		}
	}
	for(int i=m+1;i<=n;i++)
	{
		int s=n-m-(i-m);
		if(check[m]!=-INF && check[m]<=s)
		{
			sd[check[m]+1+(i-m)]=i; //cout << i << " " << check[m]+1+(i-m)<< endl;
		}
		else
		{
			int d=belong[m];
			int id=(root[d].second)[m]; 
			id+=s+1; 
			id%=(root[d].first.size());
			sd[n-m+(root[d].first)[id]+1]=i;
		}
	}
	for(int i=0;iint f;
		fscanf(xx,"%d",&f);
		f=n+1-f;
		fprintf(yy,"%d\n",sd[f]);
	}
}

まとめ

bronzeはやるだけとか面倒なだけとかの糞ゲーだったイメージですが

silverは結構面白かったです

感想

全部通って、どうぞ。

ツイートする