Codeforces #464 Div2 F. Cutlet

ややこしいけどまぁ何とか。
http://codeforces.com/contest/939/problem/F

問題

カツを焼く際、両面をN秒ずつ計2N秒焼きたい。
2N秒中、K個の区間[L[i],R[i]]においてカツをひっくり返すことができる。

両面をN秒ずつ焼いた状態にするには、最小何回焼けばよいか。
なお、区間は互いに重複しない。

解法

両面の焼き加減の差は、表を1秒焼くと+1、裏を1秒焼くと-1すると考えると、2N秒後差が0になっていればよい。

区間に入る前と入った後において、ひっくり返した回数と現在の面に対し、その状態を成す差の上限下限のペアのリストを管理しよう。
区間と区間の間は新たにひっくり返すことはできないので、今の向いている向きに焼き続けるしかない。

区間の間においてはひっくり返す回数は0～2回で十分であり、3回返す利点はない。
0回の場合は区間の間中同じ向きで焼くしかないが、1回以上ひっくり返す場合は両面を(R[i]-L[i])秒間の間任意の割合で焼くことができる。
ここから先の「差の上限下限のペアのリスト」を管理して以降。

リスト内の区間が重複部分を持つ場合、適宜連結させていくようにするとリスト内の要素数が増え過ぎずに済む。

int N,K;
int L[101],R[101];

vector<pair<int,int>> V[204][204][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	V[0][0][0].push_back({0,0});
	
	int pre=0;
	FOR(i,K) {
		
		cin>>L[i]>>R[i];
		int dif=R[i]-L[i];
		FOR(x,203) {
			FORR(v,V[i][x][0]) {
				int T=v.second+(L[i]-pre),D=v.first+(L[i]-pre);
				V[i+1][x][0].push_back({D+dif,T+dif});
				V[i+1][x+1][1].push_back({D-dif,T+dif});
				V[i+1][x+2][0].push_back({D-dif,T+dif});
			}
			FORR(v,V[i][x][1]) {
				int T=v.second-(L[i]-pre),D=v.first-(L[i]-pre);
				V[i+1][x][1].push_back({D-dif,T-dif});
				V[i+1][x+1][0].push_back({D-dif,T+dif});
				V[i+1][x+2][1].push_back({D-dif,T+dif});
			}
		}
		FOR(x,203) {
			FOR(j,2) if(V[i+1][x][j].size()) {
				vector<pair<int,int>> VV;
				sort(ALL(V[i+1][x][j]));
				FORR(r,V[i+1][x][j]) {
					if(VV.empty() || VV.back().second<r.first) {
						VV.push_back(r);
					}
					else {
						VV.back().second = max(VV.back().second,r.second);
					}
				}
				V[i+1][x][j]=VV;
			}
		}
		
		pre=R[i];
	}
	
	FOR(x,203) {
		FORR(v,V[K][x][0]) {
			int T=v.second+(2*N-pre),D=v.first+(2*N-pre);
			if(T>=0 && D<=0) return _P("Full\n%d\n",x);
		}
		FORR(v,V[K][x][1]) {
			int T=v.second-(2*N-pre),D=v.first-(2*N-pre);
			if(T>=0 && D<=0) return _P("Full\n%d\n",x);
		}
		
	}
	_P("Hungry\n");
}

まとめ

お腹空いてきますね。