kmjp's blog

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

HackerRank HourRank 22 : C. Candy Collection

あまり自信なかったけど一応通った。
https://www.hackerrank.com/contests/hourrank-22/challenges/candy-collection

問題

N個の飴が1列に並んでいる。
各飴には色T[i]と値V[i]が振られている。

この飴の列をいくつかの連続部分列に分割したい。
個々の部分列のコストは、その含まれる飴のV[i]のbitwise orとする。
また、同じ部分列に同じ色のものを複数含んではならない。

最適に部分列を整形できるとき、コストの総和の最小値を求めよ。

解法

以下を考える。GはSegTreeを使えば容易に計算できる。
F(x) := 1~xまでの飴を分割したときのコストの総和
G(x,y) := bitwise_or(V[x..y])

単純なDPとして、以下のDPが考えられる。
F(R) = min_x(F(x)+G*1
※xはT[(x+1)...R]が同じ値を複数含まない範囲を取る。

Rに対応するxの下限H(R)は容易に求められる。
H(i) := T[H(i)...i]が同じ値を複数含まない最小値
とすると、H(i) = max(H(i-1), T[j]=T[i]となるi未満で最大のj)となり、xの下限はH(R)-1となる。

H(R)<x<Rとなるxを総当たりするとTLEするので、候補を絞ろう。
まずH(R)+1は1つの候補となる。
あとはV[y+1]~V[R]はいずれもiビット目を持たず、V[y]がiビット目を持つ場合、V[y]を含むかどうかでG(x,R)の値が変化する。
よってそのようなyもxの候補として探索しよう。
V[i]<2^20なので、xの候補は20個程度までで済む。

全体でO(N*logN*log max V)でちょっと重め。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return 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 0;
		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 T[505050];
int V[505050];
int col[1010101];
ll dp[505050];
int pre[1005050];
int preb[20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(col);
	FOR(i,N) {
		cin>>T[i];
		pre[i]=col[T[i]];
		col[T[i]]=i;
	}
	
	FOR(i,N) {
		cin>>V[i];
		st.update(i,V[i]);
	}
	FOR(j,20) preb[j]=-1;
	int pp=-1;
	FOR(i,N) {
		pp=max(pp,pre[i]);
		dp[i+1]=dp[pp+1]+st.getval(pp+1,i+1);
		FOR(j,20) {
			x = max(pp,preb[j]);
			dp[i+1]=min(dp[i+1],dp[x+1]+st.getval(x+1,i+1));
			if(V[i]&(1<<j)) preb[j]=i;
		}
	}
	cout<<dp[N]<<endl;
	
}

まとめ

すんなり解けてよかった。

*1:x+1),R