Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-09-20SRM519 Div1

SRM519 Div1 250 BinaryCards

| 00:43 | SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

AとBをビット単位で上の桁から見ていき、最初にAとBのビットが異なるところより下位のビットを全て1にすれば良さそう

何となくビットをvectorに落としたらコードが汚くなった。。。

普通にビット演算すれば良かった


ソースコード

class BinaryCards {
public:
	long long largestNumber(long long A, long long B) {
		long long res;

		ll a=A, b=B;
		vector <int> ra, rb;
		while(a) {
			ra.push_back(a%2);
			a/=2;
		}
		while(b) {
			rb.push_back(b%2);
			b/=2;
		}

		int n=max(ra.size(), rb.size());
		for(int i=ra.size(); i<n; i++) {
			ra.push_back(0);
		}
		for(int i=rb.size(); i<n; i++) {
			rb.push_back(0);
		}
		reverse(ra.begin(), ra.end());
		reverse(rb.begin(), rb.end());

		vector <int> resv;
		int firstdiff=n;
		for(int i=0; i<n; i++) {
			if(ra[i]!=rb[i]) {firstdiff=i; break; }
			resv.push_back(rb[i]);
		}
		for(int i=firstdiff; i<n; i++) {
			resv.push_back(1);
		}

		res=0;
		for(int i=0; i<n; i++) {
			res*=2;
			res+=resv[i];
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110920