kmjp's blog

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

第四回 アルゴリズム実技検定 : O - 宝箱

これはPASTボス問にしては易しめ?
https://atcoder.jp/contests/past202010-open/tasks/past202010_o

問題

N個の宝箱があり、いずれも施錠されている。
i個目の宝箱を開けるとA[i]円を得る。

M人の友人がおり、i番の友人にC[i]円払うと、宝箱L[i]~R[i]が開錠される。
得た金額-友人に払う金額の最大値を求めよ。

解法

SをAの累積和とする。
dp(n) := 先頭n個の宝箱のうち、得る金額-払う金額の最大値

dp2(n) := dp(n)+S(N)-S(n) とし、SegTreeで最大値を取れるようにする。
もし友人iによる開錠を試みる場合、dp(R[i]) = dp2(n)-(S(N)-S(R[i])) となるので、R[i]の小さい順にdp(R[i])を更新していこう。

int N,M;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-(1LL<<60);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<18> st;
vector<pair<int,int>> C[202020];
ll S[202020],dp[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		S[i+1]=S[i]+x;
		dp[i+1]=-1LL<<60;
	}
	ll ret=0;
	dp[0]=0;
	st.update(0,S[N]);
	FOR(i,M) {
		int L,R,X;
		cin>>L>>R>>X;
		C[R].push_back({L-1,X});
	}
	for(i=1;i<=N;i++) {
		dp[i]=dp[i-1];
		FORR(c,C[i]) {
			int L=c.first;
			ll co=c.second;
			ll a=st.getval(L,i);
			a-=S[N]-S[i];
			dp[i]=max(dp[i],a-co);
		}
		ret=max(ret,dp[i]);
		st.update(i,dp[i]+S[N]-S[i]);
	}
	cout<<ret<<endl;
}

まとめ

割とすんなり解いてた。