tozangezan's diary

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

Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)

なぜに6問...充実しすぎて2時間でやるなら5問でも十分だと思えるセット。

A B C D E F Place
00:19 00:28 00:37 01:49 (+2) - - 34th

A:
Aですらいつもより難しい。短すぎるものを除けば一次式になるのでうんたらかんたら

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
pair<int,int> p[210000];
int f[210000];
int g[210000];

int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	int ret=mod;
	for(int i=0;i<a;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		p[i]=make_pair(y,x);
	}
	std::sort(p,p+a);
	for(int i=0;i<b;i++)scanf("%d",f+i);
	f[b]=c;
	std::sort(f,f+b+2);
	for(int i=0;i<b+1;i++){
		g[i]=f[i+1]-f[i];
	}
	std::sort(g,g+b+1);
	b++;
	int at=0;
	long long tn=0;
	long long al=0;
	for(int i=0;i<b;i++)tn+=g[i];
	tn*=3;
	for(int i=0;i<a;i++){
		if(g[b-1]>p[i].first)continue;
		while(at<b&&g[at]*2<=p[i].first){
			tn-=3LL*g[at];
			al+=g[at];
			at++;
		}
		long long cost=al+tn-(long long)(b-at)*p[i].first;

		//printf("%d: %d %I64d %d %d\n",i,at,tn,al,cost);
		if(cost<=d)ret=min(ret,p[i].second);
	}
	if(ret==mod)ret=-1;
	printf("%d\n",ret);
}

B:
左から戦艦の長さごとに漁っていくと残り候補が減っていく。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[210000];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	scanf("%s",in);
	int rem=0;
	int ren=0;
	for(int i=0;i<a;i++){
		if(in[i]=='0'){
			ren++;
		}else{
			rem+=ren/c;
			ren=0;
		}
	}
	rem+=ren/c;
	vector<int>ret;
	ren=0;
	for(int i=0;i<a;i++){
		if(rem<b)break;
		if(in[i]=='0'){
			ren++;
			if(ren%c==0){
				ret.push_back(i+1);
				rem--;
			}
		}else{
			ren=0;
		}
	}
	printf("%d\n",(int)(ret.size()));
	for(int i=0;i<ret.size();i++){
		if(i)printf(" ");
		printf("%d",ret[i]);
	}printf("\n");
}

C:
nがあるなら1~n-1が全部揃っているので、nを全部試す。他所に0があるとか0のあるべきところに0が入ってないとか、変なケースが多い。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int c[210000];
int d[210000];
int z[210000];
int sum[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);b--;
	if(a==1){
		printf("0\n");return 0;
	}
	for(int i=0;i<a;i++)scanf("%d",c+i);
	int ba=0;
	int f=0;
	for(int i=0;i<a;i++){
		if(b==i&&c[i]){
			ba++;
		}else if(b!=i&&c[i]==0){
			//ba++;
			f++;
		}else{
			d[c[i]]++;
		}
	}
	int ret=88888888;
	for(int i=1;i<a;i++){
		z[i]=z[i-1];
		if(!d[i])z[i]++;
	}
	for(int i=a-1;i>0;i--){
		sum[i]=sum[i+1]+d[i];
	}
	for(int i=1;i<a;i++){
		int t=f+sum[i+1];
		int tot=max(t,z[i]);
		ret=min(ret,ba+tot);
	}
	printf("%d\n",ret);
}

D:
実は状態数が少ない(取ったカードの枚数の差がk以下、kもO(N^0.5))ので普通にDPすればよい。
遷移先とかを間違えていて本番だったら落ちてた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[4100];
int sum[4100];
int dp[4100][200][100];
int K=95;
int ABS(int a){
	return max(a,-a);
}
int N;
int calc(int a,int b,int c){
	//if(a<0||b+K<0||c<0)printf("dame\n");
	///if(a>=4100||b+K>=200||c>=100)printf("dame\n");
	
	if(dp[a][b+K][c]!=-mod)return dp[a][b+K][c];
	int s=a;int t=a+b;
	int L=a;
	int R=N-a-b;
	if(R-L<c){
		return dp[s][t-s+K][c]=0;
	}
	int ret=-mod;
	if(s<=t){
		if(L+c+1<=R){
			ret=max(ret,-calc(s+c+1,t-(s+c+1),c+1)+sum[L+c+1]-sum[L]);
		}
		ret=max(ret,-calc(s+c,t-s-c,c)+sum[L+c]-sum[L]);
	}else{
		if(L+c+1<=R){
			ret=max(ret,-calc(s,t+c+1-s,c+1)+sum[R]-sum[R-c-1]);
		}
		ret=max(ret,-calc(s,t+c-s,c)+sum[R]-sum[R-c]);
	}
	//if(s<0||t-s+K<0||c<0)printf("%d %d %d: %d\n",s,t-s+K,c,ret);
	return dp[s][t-s+K][c]=ret;
}
int main(){
	int a;scanf("%d",&a);
	N=a;
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)sum[i+1]=sum[i]+b[i];
	for(int i=0;i<4100;i++)for(int j=0;j<200;j++)for(int k=0;k<100;k++)
		dp[i][j][k]=-mod;
	printf("%d\n",calc(0,0,1));
}

E:
フローでできることの範疇を超えている気がする。また今度。