AtCoder Grand Contest 044 A - Pay to Win

公式解説、丁寧だけど英語なんですよね…だいたいそのまま訳す感じの解説になってしまいそうですが許してください。

解法

操作を限定できる形に持ち込む

いきなりですが、操作を逆から考えます。

気持ちとしては、 $0$ からの操作を考えるとどの遷移が $N$ に向かうために最適なのか分からず、 $0, 1, ..., 10^{18}$ とものすごい状態数を考えることになります。その代わりに $N$ から始めて、操作を上手く限定して状態数を抑えながら $0$ に向かっていく、というイメージです。

操作を逆から見ると、数を $2, 3, 5$ 倍する操作は、それぞれ $2, 3, 5$ で割る操作（ただし割り切れる時に限り操作可能）と見なすことができます。 $\pm 1$ する操作はそのままです。

$N$ から操作していって今の値が $n$ であるとき、次に行う操作としては以下のパターンがあります。

そのまま $-1$ を $n$ 回繰り返して $0$ にする。
$+1$ または $-1$ の操作を何度か繰り返した後、 $2, 3, 5$ のいずれかで割る。

1番目についてはそこで操作が終了し合計コストが確定します。

2番目の操作については操作のパターンが非常に多くなりそうですが…ここでキーとなる考察をします。例えば次に $5$ で割る予定であるならば、その前の $+1$ または $-1$ の操作を $5$ 回以上行うことは無駄です。 $5$ で割る前に $+5$ または $-5$ をする代わりに、割ってから $+1$ または $-1$ をするほうがコストが少ないからです。

f:id:betrue12:20200524022017p:plain

この性質から、先ほどの2番目の操作は以下のものに限定することができます。

$d=2, 3, 5$ のいずれかについて、 $n$ に対して $d$ の倍数になるまで $+1$ の操作を行ってから $d$ で割って、 $\lceil\frac{n}{d}\rceil$ （切り上げ）を得る。
$d=2, 3, 5$ のいずれかについて、 $n$ に対して $d$ の倍数になるまで $-1$ の操作を行ってから $d$ で割って、 $\lfloor\frac{n}{d}\rfloor$ （切り捨て）を得る。

操作をこれに限定しても、遷移が6通りもあるため一見状態数が爆発しそうです。ですがこの操作によって出現する整数の個数を以下のように見積もることができます。

状態数の評価

操作によって登場する値は、 $N$ から始めて「2または3または5で割って、切り上げまたは切り捨てる」という操作を繰り返したものです。つまりある非負整数 $a, b, c$ に対して

$\displaystyle\frac{N}{2^{a}3^{b}5^{c}}$

という有理数を切り上げまたは切り捨てた整数に限られます。

この有理数が $1$ より大きくなるような $a, b, c$ の値は、それぞれ $\log_{2}N, \log_{3}N, \log_{5}N$ 以下です。ここから上記の有理数のうち $1$ より大きいものの個数を $O((\log N)^{3})$ と評価することができます。出現する整数の個数もその高々2倍に $0, 1$ の2個を加えたものとなります。実際に計算すると公式解説にあるように15万程度で抑えられることが分かります。

答えの求め方

状態数が限られていることが分かったので、答えを求めましょう。

$N$ からスタートして、コストが設定された操作を繰り返していくつかの整数を遷移し、 $0$ に到達するための最小合計コストを求める…これは最短路問題になっています。

ただし値が大きいのでそのまま距離を配列等で持つのが難しいです。C++であれば map、Pythonであれば dict 等を用いて距離を管理し、優先度付きキューを用いてダイクストラ法を回しましょう。Pythonであれば十分大きい値をデフォルト値とした defaultdict を使えば普段のダイクストラとほぼ同じように書けます。

または先ほどの操作によって必ず値は小さくなっていくため、大きい値から順番に処理していく方法でも良いです。