問題
http://community.topcoder.com/stat?c=problem_statement&pm=12588&rd=15501
解き方
監視してる数ごとに、どのような場合が成り立つか考える。
その監視している数について、成り立つすべての場合をall、カメラの数をcntとすると
all-cnt以上その場合の数が存在した時は必ず＋となり、１位上であれば？となる。
コード
class SurveillanceSystem {
public: string getContainerInfo(string containers, vector<int> reports, int L) {
int n=containers.size();
string ret="";
FORE(i,0,n)ret+='-';
int p[n];
for(int i=0;i<=n;i++){
int cnt=0;
FORE(j,0,reports.size())if(reports[j]==i)cnt++;
if(cnt==0)continue;
int all=0;
memset(p,0,sizeof(p));
for(int j=0;j+L-1<n;j++){
int tmp=0;
FORE(k,0,L)if(containers[j+k]=='X')tmp++;
if(tmp==i){
all++;
FORE(k,0,L)p[j+k]++;
}
}
FORE(j,0,n){
if(p[j]==0)continue;
if(cnt>all-p[j])ret[j]='+';
else if(ret[j]=='-')ret[j]='?';
}
}
return ret;
}
};
public: string getContainerInfo(string containers, vector<int> reports, int L) {
int n=containers.size();
string ret="";
FORE(i,0,n)ret+='-';
int p[n];
for(int i=0;i<=n;i++){
int cnt=0;
FORE(j,0,reports.size())if(reports[j]==i)cnt++;
if(cnt==0)continue;
int all=0;
memset(p,0,sizeof(p));
for(int j=0;j+L-1<n;j++){
int tmp=0;
FORE(k,0,L)if(containers[j+k]=='X')tmp++;
if(tmp==i){
all++;
FORE(k,0,L)p[j+k]++;
}
}
FORE(j,0,n){
if(p[j]==0)continue;
if(cnt>all-p[j])ret[j]='+';
else if(ret[j]=='-')ret[j]='?';
}
}
return ret;
}
};