SRM 546 250pt : KleofasTail

TopCoder

問題概要

X[n]は次のように定義される無限の長さの数列である。

  • X[n][0] = n
  • X[n][i+1] = X[n][i] is even ? X[n][i] / 2 : X[n][i] - 1

数Kが与えられる。Kを含むようなnで、A<=n<=Bであるようなものの個数を求める問題。数値は10^18以下。

考えたこととか

  • こういうのは逆から考えるのが典型。
  • Kが偶数の時Kの前はK+1か2*K、奇数の時は前は2*K。
  • えっと、これは計算量フィボナッチというアレ…？いやいや、時間全然足りない。
    • そもそも、計算量はフィボナッチにはならない。
  • すぐに解法見えないので、とりあえず手を動かして計算しよう…。
  • 全然見えない…。
  • とりあえず最初の項をaと表記すると…、aから辿っていったときすべての状態は奇数*2^kと表すことができて、そんな感じで行けるかなー？2倍と+1でなんかこうすべての整数が書けそうだし…。
  • 時間がかなり経っていたので書き始める。合わない。そもそもあまり自身の無い解法だし諦めて500行こう…。

解法

Kに対して、2*Kと2*K+1は必ず親であることを利用する。したがって、区間を[K,K+1)からスタートして次の区間を[L[i+1], R[i+1]) = [2*L[i], 2*R[i])と得ることができるので、後はこれと[A, B)の共通部分をとれば良い。

acceptされたコード

#include <algorithm>
using namespace std;

typedef long long int64;

//return intersection [x1, x2), [y1, y2)
int64 get_intersection(int64 x1, int64 x2, int64 y1, int64 y2){
	return max<int64>(0, min(y1, y2) - max(x1, x2));
}

struct KleofasTail {

	int64 countGoodSequences(int64 K, int64 A, int64 B) {
		++B;
		if(K == 0){
			return B - A;
		}

		int64 ans = 0;
		if(K&1){
			ans += (A <= K && K < B) ? 1 : 0;
			K *= 2;
		}

		int64 left = K, right = K + 2;
		for(;left <= B;){
			ans += get_intersection(A, left, B, right);
			left *= 2;
			right *= 2;
		}

		return ans;
	}

};