2014 TCO Semifinal1 DIV1 Easy - ZooExchangeProgram
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13268&rd=16187
・複数の動物がおりラベルが付けられている。
・そのうち番号がlowerからupperまでのラベルの動物を各種類最低１匹ずつ選びたい。
その他の動物については１匹も選ばないようにしたい。
・動物の選び方としては隣り合う動物については一つの集合とすることができる。
・このとき、そのような動物の選び方のうち一番少なくなる集合数を求める。
そのような選び方がない場合は−１を返す。
解き方
たとえばサンプルから選ぶラベルが２〜６のとき、
{[3, 4, 3], 1, [6, 2, 5, 7, 5, 2]}が選ぶ集合となる。
同じラベルの動物は１種類以上であれば問題ないので、
選ぶだけ選んだ方が集合が少なくなるので存在するものはすべて貪欲に選ぶ。
このとき、要素数は最大４４なので集合数は最大２２個となる。
このとき集合の選び方は2^22となり全探索が可能なので、
すべての選び方に対し、すべてのラベルの動物が含まれているか判定すればよい。
コード
long long dp[2000000];
class ZooExchangeProgram {
public: int getNumber(vector<int> label, int lower, int upper) {
int n=label.size();
int count=0;
for(int pos=0;pos<n;pos++){
while(pos<n && !(lower<=label[pos] && label[pos]<=upper))pos++;
if(pos>=n)break;
long long mask=0;
while(pos<n){
if(lower<=label[pos] && label[pos]<=upper){
mask|=(1LL<<label[pos]);
pos++;
}
else break;
}
dp[count++]=mask;
}
int ret=1e+9;
for(int i=0;i<(1<<count);i++){
long long mask=0;
FORE(j,0,count)if(i&(1<<j))mask|=dp[j];
if(mask == (((1LL<<(upper+1))-1) & ~((1LL<<lower)-1))){
ret=min(ret,__builtin_popcount(i));
}
}
return ret==1e+9 ? -1 : ret;
}
};
class ZooExchangeProgram {
public: int getNumber(vector<int> label, int lower, int upper) {
int n=label.size();
int count=0;
for(int pos=0;pos<n;pos++){
while(pos<n && !(lower<=label[pos] && label[pos]<=upper))pos++;
if(pos>=n)break;
long long mask=0;
while(pos<n){
if(lower<=label[pos] && label[pos]<=upper){
mask|=(1LL<<label[pos]);
pos++;
}
else break;
}
dp[count++]=mask;
}
int ret=1e+9;
for(int i=0;i<(1<<count);i++){
long long mask=0;
FORE(j,0,count)if(i&(1<<j))mask|=dp[j];
if(mask == (((1LL<<(upper+1))-1) & ~((1LL<<lower)-1))){
ret=min(ret,__builtin_popcount(i));
}
}
return ret==1e+9 ? -1 : ret;
}
};
