あまり自信なかったけど一応通った。
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