SRM 438 DIV1 Easy - UnluckyIntervals
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10356&rd=13803
luckyである整数の集合が与えられる。
また、unluckyな区間の取り方が定義される。
unluckyな区間とは、[A B]となるA<Bである取り方で
区間中一つもluckyな数字がない場合となる。
各整数について、unluckyな区間の取り方ができるだけ少ない方がよい。
整数ｎ個を、できるだけunluckyでない順に求める。
解き方
整数は10^9であるためすべての数字を調べられない。
ただしnは100であるため、luckyな数字の前後ｎ個ずつとってあげればよい。
unluckyな値はその前後のluckyな整数によって定義されるので
ピックアップした各整数について計算してあげればよい。
整数のピックアップについて重複しないことに注意。
コード
vector<pair<long long,long long> > p;
class UnluckyIntervals {
public: vector<int> getLuckiest(vector<int> luckySet, int n) {
int m=luckySet.size();
p.clear();
FORE(i,0,m)p.push_back(make_pair(0LL,luckySet[i]));
luckySet.push_back(0);
sort(all(luckySet));
int cur=0;
FORE(i,0,m){
for(long long j=luckySet[i]+1;j<luckySet[i+1]&&j<luckySet[i]+n;j++){
long long cost=max(0LL,(long long)(luckySet[i+1]-j)*(j-luckySet[i])-1);
p.push_back(make_pair(cost,j));
cur=j;
}
for(long long j=max(cur+1,luckySet[i+1]-n);j<luckySet[i+1];j++){
int valid=1;
FORE(k,0,m+1)if(j==luckySet[k])valid=0;
if(!valid)continue;
long long cost=max(0LL,(long long)(luckySet[i+1]-j)*(j-luckySet[i])-1);
p.push_back(make_pair(cost,j));
cur=j;
}
}
for(long long i=luckySet[m]+1;i<luckySet[m]+n+1;i++){
p.push_back(make_pair(LONG_MAX,i));
}
sort(all(p));
vector<int> ans;
for(int i=0;i<n;i++){
ans.push_back(p[i].second);
}
return ans;
}
};
class UnluckyIntervals {
public: vector<int> getLuckiest(vector<int> luckySet, int n) {
int m=luckySet.size();
p.clear();
FORE(i,0,m)p.push_back(make_pair(0LL,luckySet[i]));
luckySet.push_back(0);
sort(all(luckySet));
int cur=0;
FORE(i,0,m){
for(long long j=luckySet[i]+1;j<luckySet[i+1]&&j<luckySet[i]+n;j++){
long long cost=max(0LL,(long long)(luckySet[i+1]-j)*(j-luckySet[i])-1);
p.push_back(make_pair(cost,j));
cur=j;
}
for(long long j=max(cur+1,luckySet[i+1]-n);j<luckySet[i+1];j++){
int valid=1;
FORE(k,0,m+1)if(j==luckySet[k])valid=0;
if(!valid)continue;
long long cost=max(0LL,(long long)(luckySet[i+1]-j)*(j-luckySet[i])-1);
p.push_back(make_pair(cost,j));
cur=j;
}
}
for(long long i=luckySet[m]+1;i<luckySet[m]+n+1;i++){
p.push_back(make_pair(LONG_MAX,i));
}
sort(all(p));
vector<int> ans;
for(int i=0;i<n;i++){
ans.push_back(p[i].second);
}
return ans;
}
};
