11月祭プログラミングコンテスト2019 : D. Boiling

このコンテストは比較的難易度が抑え目。
https://www.hackerrank.com/contests/nf-procon-2019/challenges/boiling

問題

1つの鍋でN個の食材をゆでる。
茹でる順は任意だが、同時に1つしか茹でられないし、各食材は1回に茹できらないといけない。

加熱時間を正整数Xとする。
鍋の温度は最初のX分は時間経過とともに1度ずつ上昇し、その後X分かけて1度ずつ下降する。
この計2X分間で茹でる。
茹でるべき食材のパラメータとして、必要温度Aと時間Bが与えられる。
全食材を茹でられる最小のXを求めよ。

解法

Aが高い食材ほど、鍋の温度が熱い期間、鍋の温度分布における中央の時間帯に茹でるのが良い。
そこで、逆にAが低い食材から順に、できるだけ早くゆでるケースと遅くゆでるケースを総当たりしよう。
すなわち、f(0,0)=0から初めて以下をDPで埋める。

f(n,k) := Aの低い順でn番目の食材までのうち、いくつかを加熱開始後できるだけ早くゆでて計k分かかったとき、残りの食材をできるだけ遅くゆでることにして最小で末尾の何分かかるか。

(N-1)個目まで埋めたら、最後はf(N-1,k)のkを総当たりし、真ん中にN個目の食材をゆでる場合のXの値を求めればよい。

int N;
pair<int,int> P[5050];

int from[10101];
int to[10101];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
	}
	sort(P,P+N);
	FOR(i,10100) from[i]=1<<20;
	from[0]=0;
	FOR(i,N-1) {
		FOR(x,10100) to[x]=1<<20;
		FOR(x,10100) if(from[x]<1<<20) {
			// front
			int a=max(x,P[i].first)+P[i].second;
			to[a]=min(to[a],from[x]);
			// back
			a=max(from[x],P[i].first)+P[i].second;
			to[x]=min(to[x],a);
		}
		swap(from,to);
	}
	int mi=1<<20;
	FOR(x,10100) if(from[x]<1<<20) {
		int a=max(x,P[N-1].first);
		int b=max(from[x],P[N-1].first);
		
		if(abs(a-b)>=P[N-1].second) {
			mi=min(mi,max(a,b));
		}
		else {
			y=P[N-1].second-abs(a-b);
			mi=min(mi,max(a,b)+(y+1)/2);
		}
	}
	cout<<mi<<endl;
	
}

まとめ

シンプルで良い設定。