読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 711 Div1 Easy ConsecutiveOnes

SRM

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を答えないと順位は対して上がらないのであまり影響なかった。

広告を非表示にする