Hard落としたのは残念だったけど、Mediumがかなりあっさり解けたのでレートは増加。
https://community.topcoder.com/stat?c=problem_statement&pm=14558
問題
整数n,kが与えられる。
n以上の整数で、2進数表記したとき1がk個続く箇所があるような最小の整数を求めよ。
解法
1がk個続く桁を総当たりし、解の候補を求めよう。
n中、その対象の桁がすでに1で埋まっていれば、初期状態で条件を満たす。
そうでない場合、その桁を1で埋めることで確実にnより大きな値になるので、埋めた桁より下の桁はすべて0としたものが解の候補となる。
class ConsecutiveOnes { public: long long get(long long n, int k) { ll ret=1LL<<60; for(int i=0;i+k<=55;i++) { ll mask=((1LL<<k)-1)<<i; if((n & mask)==mask) return n; ret = min(ret, (n>>(i+k)<<(i+k))|mask); } return ret; } }
まとめ
本番はもう少しややこしいコード書いてタイムロス。
ただ、どのみちHardを答えないと順位は対して上がらないのであまり影響なかった。