yukicoder : No.2067 ±2^k operations

思いついてしまえば、実装は軽め。
https://yukicoder.me/problems/no/2067

問題

非負整数nに対し、f(n)を以下のように定める。

• 変数Xの初期値をnとする。Xに対し2の累乗である正整数の加算・減算を行い、X=0とするまでに必要な最小の加減算回数

正整数Nが与えられるので、を求めよ。

解法

f(n)に対し以下が成り立つ。

• f(2k) = f(k)
• f(2k+1) = 1+min(f(k),f(k+1))
• f(4k+1) = f(2k)+1 = f(k)+1
• f(4k-1) = f(2k)+1 = f(k)+1

S(N)をf(1)～f(N)の和とする。
1～Nを、2の倍数・4で割って1余る数・4で割って3余る数で分けて考えると、
S(N) = S(N/2) + S((N+3)/4-1) + (N+3)/4 + S((N+1)/3) + (N+1)/4
となり、後はメモ化再帰で解ける。

int T;
ll N;
map<ll,ll> memo;
ll hoge(ll N) {
	if(N<=0) return 0;
	if(N==1) return 1;
	if(memo.count(N)) return memo[N];
	ll ret=0;
	ret=hoge(N/2)+hoge((N+3)/4-1)+(N+3)/4+hoge((N+1)/4)+(N+1)/4;
	return memo[N]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		cout<<hoge(N)<<endl;
	}
}

まとめ

4で割った剰余に気付けるかが鍵か。