Codeforces ECR #054 : F. Summer Practice Report

シンプルな設定ながら、考察が面倒だし一発で通る気がしない…。
http://codeforces.com/contest/1076/problem/F

問題

Nページのノートに文字を書く。
iページ目には、TをX[i]個、FをY[i]個書くが、その順は任意である。
全体を通し、(ページ跨ぎもありで)同じ文字がK個を超えないように書くことができるか判定せよ。

解法

各ページに対し、末尾にTが来るケースとFが来るケースを考え、いずれも末尾に並ぶ数を最小化することを考えてDPすればよい。
末尾に並ぶ数の最小化が割と厄介なので落ち着いて考えていこう。
具体的には末尾以外にどの程度末尾を同じ文字を入れられるかを考えていくと少し楽になる。

int N,K;
int A[303030],B[303030];

ll dp[303030][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&K);
	FOR(i,N) scanf("%d",&A[i]);
	FOR(i,N) scanf("%d",&B[i]);
	
	FOR(i,N) {
		dp[i+1][0]=dp[i+1][1]=K+1;
		ll miT=1+(B[i]/K);
		ll maT=1LL*(B[i]+1)*K;
		ll miF=1+(B[i]/K);
		ll maF=1LL*(B[i]+1)*K;
		if(dp[i][0]<=K) {
			x=K-dp[i][0];
			// T->T
			ll mi=(B[i]+K-1)/K;
			ll mai=1LL*(B[i]-1)*K+x;
			if(A[i]>=mi) dp[i+1][0]=min(dp[i+1][0],max(1LL,A[i]-mai));
			
			mi=(A[i]+dp[i][0]+K-1)/K;
			mai=1LL*A[i]*K;
			if(B[i]>=mi) dp[i+1][1]=min(dp[i+1][1],max(1LL,B[i]-mai));
			
		}
		if(dp[i][1]<=K) {
			x=K-dp[i][1];
			// F->F
			ll mi=(A[i]+K-1)/K;
			ll mai=1LL*(A[i]-1)*K+x;
			
			if(B[i]>=mi) dp[i+1][1]=min(dp[i+1][1],max(1LL,B[i]-mai));
			
			mi=(B[i]+dp[i][1]+K-1)/K;
			mai=1LL*B[i]*K;
			if(A[i]>=mi) dp[i+1][0]=min(dp[i+1][0],max(1LL,A[i]-mai));
		}
		
		//cout<<dp[i+1][0]<<" "<<dp[i+1][1]<<endl;
	}
	if(dp[N][0]>K && dp[N][1]>K) cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
	
}

まとめ

むしろ良く1ミスで済んだな。