次回以降参加未定です。
https://yukicoder.me/problems/no/680
問題
以下のステップを繰り返す。
- s=t=0とする。
- tを2倍にする。
- tをインクリメントしてもよいししなくてもよい。
- sにtを加算する。
- ステップ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でもいいかもね。