AtCoder ABC #201 (マイナビプログラミングコンテスト2021) : F - Insertion Sort

Eまではまぁまぁの速度だったが…。
https://atcoder.jp/contests/abc201/tasks/abc201_f

問題

N人の人が並んでいる。
人iには異なる番号P[i]が割り振られているので、番号が昇順となるように並び替えたい。
番号P[j]=iを持つ人に対し、任意の場所に移動するコストA[i]、左端に移動するコストB[i]、右に移動するコストC[i]が与えられる。
必要な総コストの最小値を求めよ。

解法

まず、B[i]やC[i]よりA[i]が小さいなら、B[i]やC[i]をA[i]で上書きしておこう。
dp[i] := 移動させない最大の番号の人がP[i]であるような場合の、番号P[i]以下の人を昇順に並べ替える最小コスト
とする。
その直前の移動させない人の番号がP[j]であるとき、j＜iであるならそのような遷移が可能で、そのとき
dp[i] = dp[j] + A[j+1]+A[j+2]+....+A[i-1]
と更新できる。また、この人が左端の場合は
dp[i] = B[1]+B[2]+....+B[i-1]
と更新できる。

後者はBの累積和を取っておけばO(1)で計算できるし、前者はdp[j]+sum(A[(j+1)...N])の最小値を取るSegTreeを持っておけばO(NlogN)で計算できる。
dp[i]はiの順でなく位置が左の人から計算していこう。というのも「j＜iであるならそのような遷移が可能で」という条件があるためである。

解はdp[i]+sum(C[(i+1)...N])の最小値となる。

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 min(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<<20> st;
int N;
int P[202020],R[202020];
int A[202020],B[202020],C[202020];
ll BS[202020],CS[202020],AS[202020];
ll dp[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	for(i=1;i<=N;i++) {
		cin>>A[i]>>B[i]>>C[i];
		B[i]=min(B[i],A[i]);
		C[i]=min(C[i],A[i]);
		AS[i]=AS[i-1]+A[i];
		BS[i]=BS[i-1]+B[i];
		CS[i]=CS[i-1]+C[i];
	}
	
	ll ret=1LL<<60;
	FOR(i,N) {
		dp[i]=min(BS[P[i]-1], st.getval(1,P[i])-(AS[N]-AS[P[i]-1]));
		st.update(P[i],dp[i]+AS[N]-AS[P[i]]);
		ret=min(ret,dp[i]+CS[N]-CS[P[i]]);
	}
	cout<<ret<<endl;
	
	
}

まとめ

元々45分だけ参加予定だったので、そこで解けきれない時点で賞金は対象外なのよね…。