yukicoder : No.1853 Many Operations

わかってしまうとコードは短いんだけどね。
https://yukicoder.me/problems/no/1853

問題

正整数Xに対し、f(X)は以下で定義される。
変数A=0を考える。以下の処理を任意順で行い、A=Xにするまでの最小処理回数がf(X)である。

• Aをインクリメントする
• Aをデクリメントする
• Aを2倍にする

整数Nが与えられる。f(1),f(2),....,f(N)の総和を求めよ。

解法

まずf(X)の求め方を考える。

• Xが3以下ならf(X)=X
• Xが2の倍数なら、最後に2倍にすることを考えてf(X)=1+f(X/2)
• Xが4の倍数+1なら、最後に1インクリメントすることを考えてf(X)=3+f(floor(X/4))
• Xが4の倍数-1なら、最後に1デクリメントすることを考えてf(X)=3+f(1+floor(X/4))

S(X)をf(1)...f(X)の総和とする。
1...Xを、4で割った余り毎に分けて考えると、メモ化再帰しつつXを半分または1/4にして処理できる。

ll N;
const ll mo=998244353;
map<ll,ll> memo;


ll dfs(ll N) {
	if(N<=3) return N*(N+1)/2;
	if(memo.count(N)) return memo[N];
	ll ret=6-2;
	
	int i;
	ll a=(N-1)/4;
	if(a) (ret+=3*a+dfs(a))%=mo;
	a=(N-3)/4;
	if(a) (ret+=3*a+dfs(a+1)-1)%=mo;
	a=N/2;
	if(a) (ret+=a+dfs(a))%=mo;
	
	return memo[N]=ret%mo;
	
}

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

まとめ

★４だけど、実装は簡単で考察が重め。