これも割とすんなり。
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)でいいじゃん、と気づくまでに少し時間がかかりそう。