ちょっと手間取った。
https://atcoder.jp/contests/abc188/tasks/abc188_f
問題
変数Xが与えられる。以下の処理を繰り返しYにしたい。最小処理回数は何回か。
- Xに1加算する
- Xに1減算する
- Xを2倍にする
解法
減らす手段は1通りなので、X≧Yなら(X-Y)回一択。
以降、X＜Yを考える。
自分はXに処理を施すのではなく、YをXにすることを考えた。
すなわち
- Yに1加算する
- Yに1減算する
- Yが偶数なら半分にする
の手順が取れる。
f(Y) := 今YをXにするのに必要な最小処理回数
としてf(Y)をメモ化再帰しよう。
- Y≦Xなら加算しかYを増やす手段がないのでf(Y)=X-Y
- Y＞Xの場合、以下のうち最小値を取ればよい。
- 減算だけ行うケースは(X-Y)回。
- 半分にするケースは、
- Yが偶数なら1+f(Y/2)回
- Yが奇数なら加算か減算後半分にするので、min(2+f*1回
ll X,Y;
map<ll,ll> M;
ll dfs(ll v) {
if(M.count(v)) return M[v];
if(v<=X) return M[v]=X-v;
M[v]=v-X;
if(v%2==0) {
M[v]=min(M[v],1+dfs(v/2));
}
else {
M[v]=min(M[v],2+dfs((v+1)/2));
M[v]=min(M[v],2+dfs((v-1)/2));
}
return M[v];
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>X>>Y;
if(Y<=X) {
cout<<X-Y<<endl;
return;
}
cout<<dfs(Y)<<endl;
}
まとめ
別にXとY逆にする必要もなかったかな。
*1:Y+1)/2),2+f((Y-1)/2
