問題
http://community.topcoder.com/stat?c=problem_statement&pm=8576&rd=13507
・整数Ｎが与えられる。
・整数Ｎを２進数にしたときの１の数が同じで、かつＮより大きい最小の数を求める。
解き方
法則が少し複雑。
サンプルを見てみると、以下のことがわかる。
①右から走査し、最初に１が存在したらそこから次に０が出る箇所が１になる。
②１にした箇所より右を、それまで残っている１の分だけ右から詰める。
ビット列走査により以下のように求められる。
最初に１が存在する箇所：N & -N(=x)
０から１にする箇所 ：~(N+x=y)&N(=z)
１にした箇所から左部分：y(=N+x)
１にした箇所より右部分：z/x>>1
コード
class NextNumber {
public: int getNextNumber(int N) {
int x=N&(-N);
int y=N+x;
int z=N&(~y);
return y|(z/x>>1);
}
};
public: int getNextNumber(int N) {
int x=N&(-N);
int y=N+x;
int z=N&(~y);
return y|(z/x>>1);
}
};
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 NextNumber {
public: int getNextNumber(int N) {
int pos=0;
while( (N&(1<<pos))==0)pos++;
N-=(1<<pos);
int cnt=0;
while(N&(1<<(pos+1))){
pos++;
cnt++;
N-=(1<<pos);
}
N+=(1<<(pos+1));
FORE(i,0,cnt)N+=(1<<i);
return N;
}
};
#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 NextNumber {
public: int getNextNumber(int N) {
int pos=0;
while( (N&(1<<pos))==0)pos++;
N-=(1<<pos);
int cnt=0;
while(N&(1<<(pos+1))){
pos++;
cnt++;
N-=(1<<pos);
}
N+=(1<<(pos+1));
FORE(i,0,cnt)N+=(1<<i);
return N;
}
};
Share this
Related Posts
SRM 390 DIV1 Easy - ConcatenateNumber
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8589&rd=11124
解き方
そのままの整数でシミュレーションすると計算量が- SRM574 DIV2 -Level2
問題
①数字が二つ与えられる。
②プレイヤーは一つ目の数字を１０で割る、もしくは逆にすることができる。
③上記の操作によって、２つ目の数字にするとき、最小の操作回数を求める。
２つ目の数字にできないときはー１を返す。
解き方
- SRM 151 DIV1 Easy - Archimedes
問題
http://community.topcoder.com/stat?c=problem_statement&pm=1693&rd=4560
円周率を正多角形から求めたい。
円の外周は２＊円周率＊半径の長さ
- SRM 495 DIV1 Easy - ColorfulCards
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11302&rd=14424
解き方
すべての状態について、満たすすべての整数を調