Codeforces ECR #103 : F. Lanterns

シンプルな問題設定ではあるけども。
https://codeforces.com/contest/1476/problem/F

問題

N個の電灯が等距離で並んでおり、i番の電灯は座標iにある。
各電灯iは強さP[i]が設定されている。
電灯を左右どちらかに向けることで、区間[i-P[i],i-1]か[i+1,i+P[i]]のいずれかを照らすことができる。

すべての電灯の位置を照らすことができるか判定し、可能なら電灯の左右の向け方を示せ。

解法

以下を考える。
dp[i] := i番目までの電灯の位置を定めたとき、左端から右側どこまで埋められるか

• dp[i]＞iのとき、i+1番目の電灯は右を向けてよい。
• dp[i]＜iのとき、左向きにするとdp[i]+1までをカバーしてくれる最大の電灯jを求めよう。その場合、電灯jは左向き、電灯(i+1)～(j-1)は右向きにすると考えられる。

上記手順を区間最小値・最大値を取るSegtreeを持ち更新していく。

template<class V,int NV> class SegTree_mi {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_mi(){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]);
	}
	void set(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	static V const def=-(1<<30);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_ma(){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]);
	}
	void set(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int T,N;
int P[303030];
int dp[303030];
int pre[303030];
SegTree_mi<int,1<<20> smi;
SegTree_ma<int,1<<20> sma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		sma.set(0,0);
		smi.set(0,0);
		FOR(i,N) {
			cin>>P[i+1];
			if(P[i+1]) {
				sma.set(i+1,i+1+P[i+1]);
			}
			else {
				sma.set(i+1,-1);
			}
			smi.set(i+1,1<<20);
		}
		dp[0]=0;
		for(i=1;i<=N;i++) {
			dp[i]=-1<<20;
			//左向きにした場合
			x=smi.getval(max(0,i-P[i]-1),N+1);
			if(x<1<<20) {
				y=max(sma.getval(x+1,i),i-1);
				if(y>dp[i]) {
					dp[i]=y;
					pre[i]=x;
				}
			}
			
			if(dp[i-1]>=i&&dp[i]<max(dp[i-1],i+P[i])) {
				dp[i]=max(dp[i-1],i+P[i]);
				pre[i]=-1;
			}
			if(dp[i-1]>=dp[i]) {
				dp[i]=dp[i-1];
				pre[i]=-1;
			}
			if(dp[i]>N) dp[i]=N;
			smi.update(dp[i],i);
		}
		if(dp[N]!=N) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
			string S;
			int cur=N;
			while(cur) {
				if(pre[cur]==-1) {
					cur--;
					S.push_back('R');
				}
				else {
					x=pre[cur];
					cur--;
					S.push_back('L');
					while(cur>x) cur--,S.push_back('R');
				}
			}
			reverse(ALL(S));
			cout<<S<<endl;
		}
	}
}

まとめ

考え方がわかればそこまで難しくはないけども、なんか本番のAC数少ない。