yukicoder : No.680 作れる数

次回以降参加未定です。
https://yukicoder.me/problems/no/680

問題

以下のステップを繰り返す。

1. s=t=0とする。
2. tを2倍にする。
3. tをインクリメントしてもよいししなくてもよい。
4. sにtを加算する。
5. ステップ2に戻るか終了する。

整数Nが指定されたとき、終了時のsの値がNとなるようにできるか。

解法

N=10の例を取ると、tの2進数表記の遷移はこうなっている。

1ループ目 t=  1
2ループ目 t= 11
3ループ目 t=110

iループ目で1インクリメントした場合、i+1ループ目で2、i+2ループ目で4…とsに加算されていく。
つまり、あるループで1インクリメントするということは最終的にsに2進数表記で全桁1の値を加算することに等しい。
また、1ループでは1回しかインクリメントできないので、同じ値を2回加算することはない。

よってNから(2^30-1)、(2^29-1)、(2^28-1)…を貪欲に引けるだけ引いていき、最後0にできれば条件を満たせる。

ll N;

void solve() {
	int i,j,k,l,r,y; string s;
	
	cin>>N;
	for(i=30;i>=1;i--) if(N>=(1<<i)-1) N-=(1<<i)-1;
	if(N==0) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

まとめ

これ★2.5で、No.679が★3でもいいかもね。