Codeforces #688 Div2 F. Even Harder

本番ちょっと間に合わず。
https://codeforces.com/contest/1453/problem/F

問題

Nマスの双六を考える。
各マスiには整数A[i]が書かれている。
1番目のマスからN番目のマスまで駒を移動したい。
i番のマスにいる駒は、1～A[i]個先のマスのいずれかに移動できる。

ここで、移動経路が1通りに限定されるよう、いくつかのA[i]を0にしたい。
最小何個のA[i]を0にすればよいか。

解法

前処理として、「このマスに立つとN番のマスにたどり着けない」というところは気にしなくてよいので、A[i]=0で上書きしておく。

dp(a,b) := aにいる駒が、次bに移動する場合に、最後駒がN番のマスにたどり着くまでにA[i]=0としなければいけないマスの最小値
とする。dp(1,*)の最小値が解となる。
dp(a,b)を考えるとき、bの次にcに遷移するとすると、

• b=Nなら、dp(a,b)はA[a+1]…A[b-1]のうち0以外の個数
• b＜Nなら、c＞a+A[a]であるcに対し、dp(a,b)は(A[a+1]…A[c-1]のうち0以外の個数 -1)+dp(b,c)の最小値

となる。
あとは上記処理をRMQなど使い求めて行こう。

int T;
int N;
int A[3030];
int can[3030],cost[3030];
int dp[3030][3030];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	void reinit(){FORR(v,val) v=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<int,1<<12> st[3030];
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		
		cin>>N;
		FOR(i,N) {
			cin>>A[i+1];
			cost[i+1]=0;
		}
		
		
		can[N]=1;
		for(i=N-1;i>=1;i--) {
			can[i]=0;
			
			for(x=i+1;x<=i+A[i];x++) can[i]|=can[x];
			if(can[i]==0) A[i]=0;
		}
		
		
		dp[N][N]=0;
		for(i=N-1;i>=1;i--) if(can[i]) {
			int del=0;
			st[i].reinit();
			for(x=i+1;x<=i+A[i];x++) {
				if(x==N) {
					dp[i][x]=cost[x];
				}
				else if(can[x]==0||i+A[i]>=x+A[x]) {
					dp[i][x]=1<<30;
				}
				else {
					dp[i][x]=st[x].getval(i+A[i]+1,x+A[x]+1)+cost[x];
				}
				cost[x]++;
				//cout<<i<<x<<" "<<dp[i][x]<<endl;
				st[i].update(x,dp[i][x]);
			}
		}
		
		int ret=1<<20;
		for(x=2;x<=1+A[1];x++) ret=min(ret,dp[1][x]);
		cout<<ret<<endl;
		
	}
}

まとめ

Div2のFにしては簡単？