Codeforces #1053 : Div1. C. Limited Edition Shop

C問題だけどちょっと難しめ。
https://codeforces.com/contest/2150/problem/C

問題

店にN個の商品があり、その価値V[i]が与えられる。
AliceとBobはそれぞれ商品の好みの順番を持ち、異なる場合がある。

これからAliceとBobのいずれかが来る、ということがN回行われる。
その際、両者は残った商品のうち、最も好みの商品１つを買って帰る。
Aliceが買って帰る可能性のある、商品価値の総和の最大値を求めよ。

解法

もしAliceがある商品集合Sを買ったとする。
その際、Aliceが出に入らなかった商品のうち、Sのいずれかより好みのものがあった場合、それはBobにとっても寄り好みだった場合に限られる。(そうでない場合、AliceとBobが選ぶ商品は逆のはずである)

dp(i,j) := Aliceにとってi番目に好みの商品を買ったとき、そこまでBobが買った最大の好みは(Aliceにとって)j番目のものだったとするときの、Aliceのあり得る価値の最大値
とする。このテーブルをSegTreeを使いin-placeで埋めて行こう。

int T,N,V[202020],A[202020],B[202020];
int V2[202020],B2[202020];

static ll const def=-1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>V[i];
			st.update(i+1,i+2,-st.getval(i+1,i+2)-(1LL<<40));
		}
		st.update(0,1,-st.getval(0,0+1));
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
		}
		FOR(i,N) {
			cin>>x;
			B[x-1]=i;
		}
		FOR(i,N) {
			V2[i]=V[A[i]];
			B2[i]=B[A[i]];
		}
		FOR(i,N) {
			V[i]=V2[i];
			B[i]=B2[i]+1;
		}
		FOR(i,N) {
			ll v=st.getval(0,B[i]);
			ll a=st.getval(B[i],B[i]+1);
			if(v>a) st.update(B[i],B[i]+1,v-a);
			st.update(0,B[i],V[i]);
		}
		cout<<st.getval(0,N+1)<<endl;
		
		
		
	}
}

まとめ

これ本番出ても解けてなさそう。