問題
http://community.topcoder.com/stat?c=problem_statement&pm=13389&rd=16075
数字の数列があり、その数字を２進数にしたときの末尾の０の数のリストが与えられる。
このとき、与えられた数列のうち１ずつ増加するサブ数列の数を求める。
解き方
数列に法則がないか列挙してみる。
すると、以下のように再帰の法則があるとわかる。
１が現れるとき：０１０
２が現れるとき：０１０２０１０
３が現れるとき：０１０２０１０３０１０２０１０
よって、与えられた数列の全てのサブ数列に対し、以下の法則が成り立つか
再帰を用いてチェックすればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PotentialArithmeticSequence {
public:
bool can(vector<int> d){
if(d.size()==1)return true;
int p= d[0]==0 ? 0 : 1;
int n=d.size();
vector<int> next;
FORE(i,0,n){
if(i%2==p){
if(d[i]!=0)return false;
}
else{
if(d[i]==0)return false;
next.push_back(d[i]-1);
}
}
return can(next);
}
int numberOfSubsequences(vector<int> d) {
int ret=0;
int n=d.size();
FORE(i,0,n)FORE(j,i,n){
vector<int> cur;
FORE(k,i,j+1)cur.push_back(d[k]);
if(can(cur))ret++;
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PotentialArithmeticSequence {
public:
bool can(vector<int> d){
if(d.size()==1)return true;
int p= d[0]==0 ? 0 : 1;
int n=d.size();
vector<int> next;
FORE(i,0,n){
if(i%2==p){
if(d[i]!=0)return false;
}
else{
if(d[i]==0)return false;
next.push_back(d[i]-1);
}
}
return can(next);
}
int numberOfSubsequences(vector<int> d) {
int ret=0;
int n=d.size();
FORE(i,0,n)FORE(j,i,n){
vector<int> cur;
FORE(k,i,j+1)cur.push_back(d[k]);
if(can(cur))ret++;
}
return ret;
}
};
Share this
Related Posts
SRM 551 DIV1 Easy - ColorfulChocolates
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12137&rd=15173
解き方
各アルファベットごとに最大の連続数を考え、最- SRM 437 DIV1 Easy - TheSwap
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10369&rd=13699
解き方
全探索可能な問題。
setとvectorを利
- SRM 439 DIV1 Easy - PouringWater
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747
N個のボトルがあり、最初は１Ｌだけ水が入っている。
ここで同
- SRM 596 DIV1 Easy - IncrementAndDoubling
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12790&rd=15708
・求める整数の集合が与えられる。
・オペレーションはひとつの