kmjp's blog

競技プログラミング参加記です

TopCoder SRM 771: Div1 Medium TwoMonthScheduling

うーんもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=15829

問題

N個の仕事を行いたい。
各仕事は2か月連続で行う必要があり、1か月目はA[i]人、2か月目はB[i]の人を必要とする。
複数の仕事を同時に行うことはできるが、先の仕事を追い越すことはできない。

W人の人で全仕事を行うのに最低何か月かかるか。

解法

まず、AやBの累積和を取っておく。
以下をそれぞれ考える。
f(R) := R番目までの仕事を完了する最短時間。
g(L,R) := 最終月に[L,R]の区間の仕事を行う場合に、R番目までの仕事を完了する最短区間

fは単調増加で、gもLを決めるとRに対し単調増加である。

g(L,R)の次の遷移を考える。

  • 最終月に[L,R]以外の仕事を行わない場合を考えるとf(R) = min(g(L,R))
  • 最終月に、新たに[(R+1),X]の区間の1か月目の仕事をかぶせる場合、g(R+1,X)=min(g(L,R)+1, f(R)+2)
    • なお、この時[(R+1),X]の1か月目の仕事と[L,R]の2か月目の仕事がW人以下で賄え、[(R+1),X]の2か月目の仕事もW人で賄えることを確認しなければならない。

[L,R]に対しXを総当たりするとO(N^3)かかりTLEするが、尺取り法の要領でXを求めるとO(N^2)で収まる。

int L0,L1,L;
int A[5050];
int B[5050];
ll SA[5050];
ll SB[5050];
int dp[5050][5050];

class TwoMonthScheduling {
	public:
	int minimumMonths(int workers, vector <int> firstMonth0, vector <int> firstMonth1, vector <int> secondMonth0, vector <int> secondMonth1) {
		L0 = firstMonth0.size();
		L1 = firstMonth1.size();
		int i0,i1,i;
		FOR(i1,L1) FOR(i0,L0) {
			A[i1*L0+i0+1]=min(workers, firstMonth0[i0]^firstMonth1[i1]);
			B[i1*L0+i0+1]=min(workers, secondMonth0[i0]^secondMonth1[i1]);
			SA[i1*L0+i0+1]=SA[i1*L0+i0]+A[i1*L0+i0+1];
			SB[i1*L0+i0+1]=SB[i1*L0+i0]+B[i1*L0+i0+1];
		}
		int N=L0*L1;
		int x,y,W=workers;
		FOR(x,N+2) FOR(y,N+2) dp[x][y]=101010;
		int mi=101010;
		dp[1][0]=0;
		int L,R,R2;
		for(L=1;L<=N;L++) {
			int R2=0;
			for(R=N;R>=L;R--) dp[L][R]=min(dp[L][R],dp[L][R+1]);
			for(R=L;R<=N;R++) if(SA[R]-SA[L-1]<=W && SB[R]-SB[L-1]<=W) {
				//completely new
				dp[L][R]=min(dp[L][R],dp[L][0]+2);
				//fin
				dp[R+1][0]=min(dp[R+1][0],dp[L][R]);
				for(R2=max(R+1,R2);R2<=N;R2++) {
					if(SB[R]-SB[L-1]+SA[R2]-SA[R]>W || SB[R2]-SB[R]>W) break;
				}
				while(R2>R && (SB[R]-SB[L-1]+SA[R2]-SA[R]>W || SB[R2]-SB[R]>W)) R2--;
				dp[R+1][R2]=min(dp[R+1][R2],dp[L][R]+1);
			}
			mi=min(mi,dp[L][N]);
		}
		mi=min(mi,dp[N+1][0]);
		
		return mi;
		
	}
}

まとめ

O(N^3)をいかにO(N^2)にするかという問題。