kmjp's blog

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

Google Code Jam 2017 Round 1C : B. Parenting Partnering

これも割とすんなり。
https://code.google.com/codejam/contest/3274486/dashboard#s=p1

問題

毎日24時間1440分の間、夫婦2名で子供の世話をする。
両者、子供の世話をできない時間帯が存在する。

世話をする時間を720分ずつ均等にしつつ、1日あたり世話を交代する回数が最小となるようにせよ。

解法

以下をDPしていけばよい。
f(minute,first,cur,x) := 最初に世話をしていたのがfirst側で、日の初めからminute分後まで経った時点で現在cur側が世話しており、minute分中x分夫が世話していた場合の最小交代回数

fの状態としてはO(T^2) (Tは時間の最大値1440)程度で、状態遷移は交代するしないの2通りなので結局O(T^2)で解ける。
日の最後と最初で担当が異なる場合、そこでも交代が1回生じるので注意。そのためfirstを覚えている。

int A[2];
int NG[2][1540];

int from[1500][2][2];
int to[1500][2][2];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	ZERO(NG);
	cin>>A[0]>>A[1];
	FOR(i,2) {
		while(A[i]--) {
			cin>>x>>y;
			while(x<y) NG[i][x++]=1;
		}
	}
	FOR(i,1440) from[i][0][0]=from[i][0][1]=from[i][1][0]=from[i][1][1]=5050;
	from[0][0][0]=from[0][1][1]=0;
	FOR(i,1440) {
		FOR(j,1440) to[j][0][0]=to[j][0][1]=to[j][1][0]=to[j][1][1]=5050;
		FOR(x,1440) {
			y=i-x;
			if(y<0) continue;
			FOR(j,2) {
				// x->x
				if(NG[0][i]==0 && x<720) to[x+1][j][0]=min(to[x+1][j][0],from[x][j][0]);
				// x->y
				if(NG[1][i]==0 && y<720) to[x][j][1]=min(to[x][j][1],from[x][j][0]+1);
				// y->x
				if(NG[0][i]==0 && x<720) to[x+1][j][0]=min(to[x+1][j][0],from[x][j][1]+1);
				// y->y
				if(NG[1][i]==0 && y<720) to[x][j][1]=min(to[x][j][1],from[x][j][1]);
			}
		}
		swap(from,to);
	}
	
	int ret=5050;
	ret=min(ret,from[720][0][0]);
	ret=min(ret,from[720][0][1]+1);
	ret=min(ret,from[720][1][0]+1);
	ret=min(ret,from[720][1][1]);
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

O(T^2)でいいじゃん、と気づくまでに少し時間がかかりそう。