AtCoder ABC #353 : G - Merchant Takahashi

Fの方が難しいかも。
https://atcoder.jp/contests/abc353/tasks/abc353_g

問題

1～N番の町がある。
i番からj番の町に移動するにはC*abs(i-j)のコストがかかる。
ここでM回お金が得られるタイミングがあり、i回目はT[i]の町にいるとP[i]のお金が得られる。

最初に1番の町にいるとき、最適な移動をした場合に(得られるお金)-(コスト)の最大値を求めよ。

解法

dp(m,n) := m回目のタイミングを迎えた時点で、n番の町にいる状態における(得られるお金)-(コスト)の最大値
とする。
SegTreeを2つ用意し、以下の2つの値における区間最大値を算出できるようにしよう。

• dp(m,n) - C*n
• dp(m,n) + C*n

m+1回目のタイミングでお金を得ようとする場合、dp(m+1,T[m+1])は以下の最大値となる。

• T[m+1]番より小さな番号の町からT[m+1]番の町に移動する場合、max(dp(m,n)+C*n) - C*T[m+1] + P[m+1]
• T[m+1]番より大きな番号の町からT[m+1]番の町に移動する場合、max(dp(m,n)-C*n) + C*T[m+1] + P[m+1]

上記は2つのSegTreeを使いO(logN)で求められる。

int N,M;
ll C;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-(1LL<<62);
	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<<20> Lst,Rst;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	Lst.update(0,0);
	Rst.update(0,0);
	cin>>M;
	ll ret=0;
	while(M--) {
		int T;
		ll P;
		cin>>T>>P;
		T--;
		ll ma=max(Lst.getval(0,T)-C*T,Rst.getval(T,N)+C*T)+P;
		ret=max(ret,ma);
		Lst.update(T,ma+C*T);
		Rst.update(T,ma-C*T);
	}
	cout<<ret<<endl;
}

まとめ

最近参加者1万人超えるんだな。