TopCoder SRM 714 Div1 Medium NAddOdd

自分含めゴリ押した人が多そう。
https://community.topcoder.com/stat?c=problem_statement&pm=14408

問題

コラッツ予想の変形を考える。
f(X)は以下のような関数である。

• Xが偶数ならf(X)=X/2
• Xが奇数なら定数Kに対しf(X)=X+K

ある整数Xに対し、値がK以下になるまでfを適用することを考える。
その回数をg(X)とする。

整数L,R,Kが与えられるので、sum(g(L),g(L+1),....,g(R))を求めよ。

解法

h(X) := sum(g(1),g(2),...,g(X))とすると、h(R)-h(L-1)が解となる。
あとはこのh(X)の求め方を考えよう。

[1,X]のうち、

• [1,K]はfを適用する必要がないため、f(X)に寄与しない。
• [K+1,X]のうち偶数に関してはfを適用すると[(K+1)/2,X/2]の区間になる。
  • よって偶数の数をNEとするとh(X) += NE + h(X/2)と考えられる。(正確にはh(X/2)-h((K+1)/2-1)かもしれないが、後者は0なので考えなくてよい)
• [K+1,X]のうち奇数に関してはfを2回適用すると[K+1,(X+K)/2]の区間になる。
  • よって奇数の数をNOとするとh(X) += 2*NO + h((X+K)/2)と考えられる。

さて、h(X)を求めるにはh(X/2)とh((X+K)/2)を求める必要があることがわかった。
ここで以下どちらのアプローチでも正解できる。

• メモ化してそれぞれ頑張る。
  • 引数Xに登場する数のバリエーションはそこまで多くないので、unordered_mapを使ったり定数倍の最適化を頑張って、本番1.96sで通った。
• v∈[(X/2+1)...(X+K)/2]に関しては、直接g(v)を求めてしまう。
  • Kはあまり大きくないので、求めるべきvの数は多くない。
  • こうすると、上記のようにh(X/2)とh((X+K)/2)を別々に求める必要はなく、h(X/2)を求めればよくなるので状態が増えず、400ms程度で通る。

class NAddOdd {
	public:
	int num(ll V,ll K) {
		int ret=0;
		while(V>K) {
			if(V&1) V=(V+K)/2, ret+=2;
			else V/=2, ret++;
		}
		return ret;
	}
	
	ll hoge(ll X,ll K) {
		if(X<=K) return 0;
		
		ll neven = X/2-K/2;
		ll nodd = X-K-neven;
		ll ret = neven + 2*nodd + 2*hoge(X/2,K);
		
		for(ll v=X/2+1; v<=(X+K)/2;v++) ret += num(v,K);
		return ret;
	}
	
	long long solve(long long L, long long R, int K) {
		return hoge(R,K)-hoge(L-1,K);
	}
}

まとめ

終わってみるとコードは短い。