Codeforces #426 Div1 B. The Bakery

手間取ったけど解けて良かった。
http://codeforces.com/contest/833/problem/B

問題

N要素の数列Aがある。これを連続部分列K個に分割することを考える。
個々の部分列におけるスコアとは、部分列中におけるユニークな値の数とする。
総スコアの最大値を求めよ。

解法

つい先日の↓これと問題設定が近いが、解法はだいぶことなる。
TopCoderOpen 2017 Round2C Hard TreasureOfWinedag - kmjp's blog

問題から想像つくように、以下を考えよう。f(N,K)が求める値である。
f(i,k) := Aの先頭i要素をk個の分割したときのそれらの総スコアの最大値

S(L,R) := A[L...R]におけるスコア
とすると、となる。
よってf(*,k-1)からf(*,k)を求めていくことを考えよう。

区間に対し定数を加算でき、また区間の最大値を得られるSegTreeを作ろう。
f(*,k)を求める前に、SegTree上i番目の要素にf(i,k-1)がセットされるようにしておく。

今f(i,k)を考える。iを0から順にインクリメントさせながら求めていこう。
k個目の部分列の最後がi番目だとすると、この部分列A[x...i]中にA[i]以外にA[i]と同じ値が存在しないなら、A[x...(i-1)]に比べA[x...i]はスコアが1上昇する。
これをもう少しプログラムに落とし込める形にする。
pre(i)を、A[pre(i)]がA[i]と同じ値であるもののうちi未満で最大の値とする。
pre(i)＜x≦iの場合のみA[x...i]は1加算される。
よってSegTree上でも[pre(i)+1,i]の範囲に1加算したうえで、SegTree上[0,i)の範囲で最大値を検索すればそれがf(i,k)となる。

int N,K;
int A[404040];
int pre[404040];
int P[404040];

static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	void init(){
		int i;
		val.clear(); ma.clear();
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,2*NV) val[i]=ma[i]=0;
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_3<int,1<<17> st;
int dp[40404][52];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N+1) pre[i]=-1;
	FOR(i,N) {
		cin>>A[i];
		P[i]=pre[A[i]];
		pre[A[i]]=i;
		
		if(i==0) {
			dp[i][0]=1;
		}
		else {
			dp[i][0]=dp[i-1][0];
			if(P[i]==-1) dp[i][0]++;
		}
	}
	
	for(i=1;i<K;i++) {
		st.init();
		FOR(x,N) st.update(x,x+1,dp[x][i-1]);
		
		FOR(x,N) {
			st.update(P[x],x,1);
			dp[x][i]=st.getval(0,x);
		}
	}
	
	cout<<dp[N-1][K-1]<<endl;
	
	
}

まとめ

問題設定が近いのに、解き味が異なるのは興味深いね。