AtCoder ARC #085 : F - NRE

わかってしまえば単純だが。
https://beta.atcoder.jp/contests/arc085/tasks/arc085_d

問題

0/1の２値を取るN要素の数列A,Bがある。
Bは入力として与えられる。Aは初期状態ですべて0である。

ここでいくつか区間の集合を与えられる。
集合中の区間を選択することで、Aにおけるその区間内の要素を1にすることができる。
任意の数の区間を選択した場合、AとBのハミング距離の最小値を求めよ。

解法

ハミング距離は、(A[i],B[i])=(0,1)または(1,0)になっているiの数である。
これを少し変形すると、(B[i]=1であるiの数)-*1
この後ろの値は、RMQが求められれば算出可能である。

最終的にf(*,N-1)の最小値を答えればよい。

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);};
	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]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

int N;
int S[202020];
int Q;
vector<int> ev[202020];
int dp[202020];


void solve() {
	int i,j,k,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		dp[0]+=x;
		if(x==1) S[i+1]=S[i]-1;
		else S[i+1]=S[i]+1;
	}
	
	
	FOR(i,N+1) {
		if(i) dp[i]=1<<20;
		st.update(i,dp[i]+(S[N]-S[i]));
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>x>>y;
		ev[x].push_back(y);
	}
	for(i=1;i<=N;i++) {
		FORR(r,ev[i]) {
			x = min(dp[i-1]+(S[r]-S[i-1]),st.getval(i,r+1) - (S[N]-S[r]));
			if(x<dp[r]) {
				dp[r]=x;
				st.update(r,dp[r]+(S[N]-S[r]));
			}
		}
		dp[i]=min(dp[i],dp[i-1]);
		
	}
	cout<<*min_element(dp,dp+N+1)<<endl;
	
}

まとめ

こういうあとで検索しづらい問題名は特別意味がないならやめてほしいかも。
後で思い出すときも思い出しにくい…。

*1:A[i],B[i])=(1,1)となるiの数)+((A[i],B[i])=(1,0)となるiの数)となる。 最初の項は容易に求まるとして、後ろ2つの項を考えよう。 これは言い換えると、A[i]を1にするとB[i]の値によってハミング距離が+1または-1されることに相当する。 各区間P[j]を[L[j],R[j]]とする。 区間をL[j]毎に分類しよう。 以下を考える。 f(i,x) := DP過程において、L[j]≦xであるような区間に対し選択有無を判定後、A[x,i]=1である場合のハミング距離の最小値 f(i,x-1)が求まっているとき、L[j]=xであるようなjに対し、A[L[j],R[j]]を1にしたらハミング距離がどうなるかを判定しよう。 事前に以下の累積和を計算しておく。 C[i] = (B[i]=0なら+1、B[i]=1なら-1) CS[i] = sum(C[0..i]) [L[j],R[j]]を選択し、A[L[j],R[j]]=1にすることで、f(R[j],x)は以下のように遷移する。 後者はすでにi∈[L[j],R[j]]となるようなiまでA[L[j]..i]=1である場合、残りA[(i+1)..R[j]]を1にしたときのハミング距離の変動に相当する。 f(R[j],x) = min(f(R[j],x), f(R[j],x-1),f(i,x-1)+(CS[R[j]]-CS[i]