Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-07-23

KleofasTail (SRM 546 Div1Easy)

23:35 | KleofasTail (SRM 546 Div1Easy) - capythm@TopCoder を含むブックマーク はてなブックマーク - KleofasTail (SRM 546 Div1Easy) - capythm@TopCoder KleofasTail (SRM 546 Div1Easy) - capythm@TopCoder のブックマークコメント

問題概要

Kleofas Tailとは、以下の数列を指す。

  • 最初の要素は非負数 X
  • ある要素Yの次の要素は以下のように決定
    • 現要素が偶数の場合、次要素は Y/2
    • 現要素が奇数の場合、次要素は Y-1

最初の要素がA~Bの範囲の数であるKleofas Tailで、Kを含むものは何個存在するか?

http://community.topcoder.com/stat?c=problem_statement&pm=12049


解法

たとえば、5を含むKleofas Tailは5;10,11;20,21,22,23;40,41,42,43,44,45,46,47;... などである。

つまり2進数表現で 101xxxxxxxx (xは0か1、xの個数は0個以上) となるような数であれば、5を含む

ことになる。

Kが偶数の場合は要注意で、6を含むKleofas Tailは

6,7;12,13,14,15;... などになる。

つまり、6の2進数表現から1ビット削って 11xxxxxx (xは0か1、xの個数は1個以上)となる。

K=0の場合は特殊で、B-A+1を返せばいい。

上記をよく気をつけて実装すると、ループ回数がビット幅分ぐらいになって高速にカウントアップ可能。

ソースコード

#include <algorithm>
using namespace std;

class KleofasTail{
public:
  long long countGoodSequences(long long K, long long A, long long B){
    long long ret=0;
    if( K==0 ) return B-A+1;
    if( K%2==0 ) K/=2;
    else if( A<=K && K<=B ) ret++;
    long long mask=0;
    while( K <= 1000000000000000000LL ){
      K *= 2;
      mask = mask*2+1;
      long long x1 = max( K,A );
      long long x2 = min( K+mask,B );
      ret += max( x2-x1+1, 0LL );
    }
    return ret;
  }
};