Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-20SRM543 Div1

SRM543 Div1 250 EllysXors

| 19:29 | SRM543 Div1 250 EllysXors - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM543 Div1 250 EllysXors - SRM diary(Sigmar) SRM543 Div1 250 EllysXors - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

異様に速い提出者がいて若干ライブラリゲーの様相を呈する

ライブラリは持っていなかったので普通に考えた


0~NまでのXORを単に求める問題に置換する

ビットごとに考える

  • 1ビット目は 0,1,0,1,0,1,0,1,...
  • 2ビット目は 0,0,1,1,0,0,1,1,...
  • 3ビット目は 0,0,0,0,1,1,1,1,...

となるから、xビット目は2^xの周期を持つ

1ビット目は、4で割った余りで場合分けが可能

2ビット目以降は、1周期の1のビット数が2の倍数だから、周期で割った余りだけ調べればいい


書いた

合わない


こまごましたoff by one的な間違いがあった

直した

提出


遅っ・・・!


後で

unsigned intにして、ループで計算して通した人がいたと聞いて驚いた

XORって2秒間に40億回も計算できるのね・・・

計算量の見積もりに精通していれば一瞬で書けるというのは、悪くない問題設定だと思う


ソースコード

提出したバージョン

class EllysXors {
public:
	ll calc(ll x) {
		ll res=0;
		if(x%4==1 || x%4==2) res|=1;
		for(int i=1; i<40 && x; i++) {
			ll rem=x%(1LL<<(i+1));
			if(rem>=(1LL<<i)) {
				rem-=(1LL<<i);
				if(rem%2==0) res|=(1LL<<i);
			}
		}
		return res;
	}

	long long getXor(long long L, long long R) {
		long long res;

		res=calc(R)^calc(L-1);
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120520