kmjp's blog

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

Codeforces #541 Div2 G. Most Dangerous Shark

なぜDiv2 only回で3500ptとか出るんだ…。
https://codeforces.com/contest/1131/problem/G

問題

M個のドミノが左右一列に、互いに間隔1に並んで立っている。
それぞれのドミノiに対し、高さH[i]とコストC[i]が与えられる。

ドミノを1つ選択し、左右どちらかに倒すことを考える。
倒れた方向にある距離が高さ未満のドミノは同じ方向に倒れる。またこの動作は連鎖的に発生する。
ただしこの時、最初に倒したドミノの分のコストがかかる。

全ドミノを倒す最小コストを求めよ。

解法

Mが10^7と大きいので、O(M)解法を考える。

まず、各ドミノiを左右に倒した場合どこまで倒れるかL[i],R[i]をそれぞれ求めよう。
これはdequeを用いて求めることができる。

f(m) := 先頭からm番目までのドミノを倒すコスト
とする。f(m)は当然単調増加である。

m番目を左に倒す場合と、右に倒す場合を考え、最小値を取ろう。

  • 左に倒す場合、L[m]まで倒れるのでf(m) = f(L[m]-1) + C[m]
  • 直接または間接的に右に倒す場合、R[k]≧mであるようなkに対しf(m) = f(k-1)+C[k]

前者は1つしか値が無いが、後者がkの候補がいくつかある。
そこでdequeを使い{R[k],f(k-1)+C[k]}の∈をスライド最小値の要領で更新していこう。

int N,M;
vector<int> A[303030],CT[303030];
int Q;
int H[10101010];
ll C[10101010];
ll dp[10101010];

int L[10101010],R[10101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) {
		scanf("%d",&x);
		A[i].resize(x);
		CT[i].resize(x);
		FOR(j,x) scanf("%d",&A[i][j]);
		FOR(j,x) scanf("%d",&CT[i][j]);
	}
	scanf("%d",&Q);
	int cur=1;
	FOR(i,Q) {
		scanf("%d%d",&x,&y);
		FOR(j,A[x-1].size()) {
			dp[cur]=1LL<<60;
			H[cur]=A[x-1][j];
			C[cur]=CT[x-1][j]*1LL*y;
			cur++;
		}
	}
	deque<pair<int,int>> D;
	for(i=1;i<=M;i++) {
		int LM=i-(H[i]-1);
		while(D.size() && D.back().second>=LM) LM=min(LM,D.back().first), D.pop_back();
		L[i]=max(1,LM);
		D.push_back({L[i],i});
	}
	D.clear();
	for(i=M;i>=1;i--) {
		int RM=i+H[i]-1;
		while(D.size() && D.back().second<=RM) RM=max(RM,D.back().first), D.pop_back();
		R[i]=min(M,RM);
		D.push_back({R[i],i});
	}
	
	deque<pair<int,ll>> Q;
	for(i=1;i<=M;i++) {
		dp[i]=dp[L[i]-1]+C[i];
		while(Q.size()&&Q.back().first<i) Q.pop_back();
		if(Q.size()) dp[i]=min(dp[i],Q.back().second);
		
		ll co=dp[i-1]+C[i];
		if(Q.empty()||co<Q.back().second) Q.push_back({R[i],co});
		
		
	}
	cout<<dp[M]<<endl;
	
}

まとめ

O(M)にさせたいとはいえ、変わった入力方式。