読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

MultiplyAddPuzzle [SRM 707 : Div1 Med]

競技プログラミング

問題

ある数sについて以下の手順をしてある数tにしたい。

1. +aする
2. *bする

最小のステップ数は?

0 <= s,t,a,b <= 10^18

考察

1. コーナーケースがやばいので、s > t, b = 0, b = 1, a = 0らへんはうまいことやる

2. 気づくべき点が「書ける回数はあまり多くないのでは?」という所
3. 10^18が最大数なので2 <= bであれば、64回より多くは掛けないはず
4. 手順2の回数を固定して考える

5. n回*bをするとすると、以下のように問題を読み替えることができる
 t=sb^n + a(bの多項式)
6. 後はbの多項式部分が項数最小となり、かつ、以上の等式を満たすパターンを考えればいい
7. つまり、以下の問題に最終的に帰着する
 定数x = \sum^{n}_{k = 0}a_kb^k 上での \sum^{n}_{k=0}a_k の最小値
8. これは以下のようにして求まる

ll cal(ll x, ll b, int n) {
	ll res = 0;
	rep(i, 0, k) {
		res += (x % b);
		x /= b;
	}
	return res + x;
}

9. 手順2の回数を全パターン試して最小が答え
10. long longのオーバーフローに注意

参考