読者です 読者をやめる 読者になる 読者になる

Codeforces Round #366 (Div. 1)

コンテストのバランスを全く考えていない難問セットなのですが、一つ一つはICPCの大変な問題(しかもサンプルも弱い)のような存在で、ただ実装が辛いだけでした。
ちなみにMARVELはヴェノム派です。

A B C D E Place
00:16 (+1) 00:53 (+3) - - - 33rd

A:
なんて事はないやるだけ問題なのですが、iとnumを1箇所間違えました。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[310000];
int at[310000];
vector<int>v[310000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int cnt=0;
	int ind=0;
	int num=0;
	for(int i=0;i<b;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==1){
			cnt++;
			v[y].push_back(num++);
		}else if(x==2){
			while(at[y]<v[y].size()){
				if(!p[v[y][at[y]]])cnt--;
				p[v[y][at[y]]]=1;
				at[y]++;
			}
		}else{
			while(ind<y){
				if(!p[ind])cnt--;
				p[ind]=1;
				ind++;
			}
		}
		printf("%d\n",cnt);
	}
}

B:
類題はもう何個もあると思います。生きている辺が1本のときの場合分けとかが厄介ですが、サンプルには入っていません。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int x[5100];
long long dp[2][10100];
int A[5100];
int B[5100];
int C[5100];
int D[5100];

int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	b--;c--;
	for(int i=0;i<a;i++)scanf("%d",x+i);
	x[a]=mod;
	for(int i=0;i<a;i++)scanf("%d",A+i);
	for(int i=0;i<a;i++)scanf("%d",B+i);
	for(int i=0;i<a;i++)scanf("%d",C+i);
	for(int i=0;i<a;i++)scanf("%d",D+i);
	for(int i=0;i<2;i++)for(int j=0;j<10100;j++)dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=0;i<a;i++){
		int t=i%2;
		for(int j=0;j<10100;j++)dp[!t][j]=inf;
		for(int j=0;j<a*2;j++){
			if(dp[t][j]==inf)continue;
			if(i==b){
				if(j>1||(j==1&&i==a-1))dp[!t][j-1]=min(dp[!t][j-1],dp[t][j]+(long long)(j-1)*(x[i+1]-x[i])+C[i]);
				dp[!t][j+1]=min(dp[!t][j+1],dp[t][j]+(long long)(j+1)*(x[i+1]-x[i])+D[i]);
			}else if(i==c){
				if(j>1||(j==1&&i==a-1))dp[!t][j-1]=min(dp[!t][j-1],dp[t][j]+(long long)(j-1)*(x[i+1]-x[i])+A[i]);
				dp[!t][j+1]=min(dp[!t][j+1],dp[t][j]+(long long)(j+1)*(x[i+1]-x[i])+B[i]);
			}else{
				dp[!t][j+2]=min(dp[!t][j+2],dp[t][j]+(long long)(j+2)*(x[i+1]-x[i])+B[i]+D[i]);
				if(j>1)dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+min(B[i]+C[i],A[i]+D[i]));
				else if(j==1){
					if(b<i)dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+A[i]+D[i]);
					else dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+C[i]+B[i]);
				}
				if(j>2||(j==2&&i==a-1))dp[!t][j-2]=min(dp[!t][j-2],dp[t][j]+(long long)(j-2)*(x[i+1]-x[i])+A[i]+C[i]);
			}
		}
	}
	printf("%I64d\n",dp[a%2][0]);
}

C:
¬とかを無視すれば輪と直線しかないので、一次元にできてあとはありがちなDPをするだけですが、結構実装量が多いです。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int L[110000];
int R[110000];
vector<int>g[110000];
int ABS(int a){
	return max(a,-a);
}
int num=1;
int ord[110000];
int lm[110000];
int v[110000];
pair<int,int> p[110000];
long long dp[110000][2][2][2];
vector<int>q[110000];
int main(){
	int a,b;scanf("%d%d",&b,&a);
	for(int i=0;i<b;i++){
		int x;scanf("%d",&x);
		if(x==1){
			scanf("%d",L+i);
		}else{
			scanf("%d%d",L+i,R+i);
		//	if(ABS(L[i])<ABS(R[i]))swap(L[i],R[i]);
			if(ABS(L[i])!=ABS(R[i])){
				g[ABS(L[i])].push_back(ABS(R[i]));
				g[ABS(R[i])].push_back(ABS(L[i]));
			}
		}
	}
	for(int i=1;i<=a;i++)v[i]=-1;
	for(int i=1;i<=a;i++)p[i]=make_pair(g[i].size(),i);
	std::sort(p+1,p+a+1);
	for(int i=1;i<=a;i++){
		int at=p[i].second;
		if(~v[at])continue;
		int id=at;
		int tl=num;
		if(p[i].first!=2)tl=-1;

		while(1){
			bool ok=false;
			ord[num]=id;
			v[id]=num++;
			lm[id]=tl;
			for(int j=0;j<g[id].size();j++){
				if(~v[g[id][j]])continue;
				ok=true;
				id=g[id][j];
				break;
			}
			if(!ok)break;
		}
	}
	for(int i=0;i<b;i++){
		q[max(v[ABS(L[i])],v[ABS(R[i])])].push_back(i);
	}
//	for(int i=1;i<=a;i++)printf("%d ",v[i]);
//	printf("\n");
	dp[0][0][0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<2;l++){
			if(!dp[i][j][k][l])continue;
			for(int m=0;m<2;m++){
				int tl=l;
				int tk=m;
				int tj=j;
				if(lm[ord[i+1]]==i+1)tj=m;

				for(int t=0;t<q[i+1].size();t++){
					int ql=L[q[i+1][t]];
					int qr=R[q[i+1][t]];
					if(ABS(ql)==ord[i+1]){
						if(qr==0){
							if(ql>0&&m)tl^=1;
							if(ql<0&&!m)tl^=1;
						}else if(ABS(qr)==ord[i+1]){
							if(((ql<0)^m)||((qr<0)^m))tl^=1;
						}else if(ABS(qr)==ord[i]){
							if(((ql<0)^m)||((qr<0)^k))tl^=1;
						}else{
							if(((ql<0)^m)||((qr<0)^j))tl^=1;
						}
					}else{
						if(ABS(ql)==ord[i]){
							if(((qr<0)^m)||((ql<0)^k))tl^=1;
						}else{
							if(((qr<0)^m)||((ql<0)^j))tl^=1;
						}
					}
				}
				dp[i+1][tj][tk][tl]=(dp[i+1][tj][tk][tl]+dp[i][j][k][l])%mod;
			}
		}
	}
	long long ret=0;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++)ret+=dp[a][i][j][1];
	ret%=mod;
	printf("%d\n",(int)ret);
}