Codeforces #1117 : Div2. E. Busy Beaver

これは途中ミスこそあったものの、解法自体はすんなり出せたな。
https://codeforces.com/contest/2257/problem/E

問題

プレイヤーは初期状態でXのお金を持つ。

ここで、N個の建物を建てるプランがあり、各建物には異なる階数が設定されていて、階ごとに建築コストと立てたあとの利益が設定されている。

ある階を建築するには、当然下の階を先に建築する必要がある。
また、コスト以上のお金を所有している必要があり、建築完了すると即座に利益分のお金が手に入る。
建築の順番は任意で、途中他の建物に移ってもよい。

最も高い建物を建てるられるのは、どの建物で何回か。

解法

各建物を最大まで高くする場合を総当たりする。
それに先立ち、まずお金を増やすことはどの建物を建てる場合も有効なのでそれを行っておこう。
建物ごとにコストと利益の累積和を考え、利益の方が多くなるタイミングがあれば、コストの低い順に適宜採用して建築していく。

あとは、それ以上お金が増えることはないので、各建物を総当たりして全額betし、どこまで高くできるか求める。

int T;
int N;
ll X;
int M[202020];
vector<ll> A[202020],B[202020];
vector<array<ll,4>> V[202020];
int num[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X;
		priority_queue<array<ll,4>> Q;
		FOR(i,N) {
			cin>>M[i];
			A[i].resize(M[i]);
			FORR(a,A[i]) cin>>a;
			B[i].resize(M[i]);
			FORR(a,B[i]) cin>>a;
			
			V[i].clear();
			ll sum=0,mi=0;
			num[i]=0;
			FOR(j,M[i]) {
				sum-=A[i][j];
				mi=min(mi,sum);
				sum+=B[i][j];
				if(sum>0) {
					V[i].push_back({mi,sum,i,j+1});
					sum=mi=0;
				}
			}
			if(V[i].size()) {
				Q.push(V[i][0]);
			}
		}
		while(Q.size()) {
			auto p=Q.top();
			Q.pop();
			if(X+p[0]<0) break;
			X+=p[1];
			i=p[2];
			num[i]++;
			if(num[i]<V[i].size()) {
				Q.push(V[i][num[i]]);
			}
		}
		int ma=0,ret=1;
		FOR(i,N) {
			ll cur=X;
			int floor=(num[i]==0?0:V[i][num[i]-1][3]);
			while(floor<M[i]) {
				if(cur<A[i][floor]) break;
				cur-=A[i][floor];
				cur+=B[i][floor];
				floor++;
			}
			if(floor>ma) {
				ma=floor;
				ret=i+1;
			}
		}
		cout<<ma<<" "<<ret<<endl;
	}
}

まとめ

なんでBeaverの設定入れたんだろうな。