Clipped Collatz Cost

解説

$1,2,\ldots,K$ を頂点とする重み付き有向グラフを考えます。

各整数 $x$ から、操作 $1$ 後の値 $\min(3x+1,K)$ と、操作 $2$ 後の値 $\left\lceil x/2\right\rceil$ への辺を張り、その重みを操作にかかるコストとします。

このグラフにおいて、$C_i$ は頂点 $i$ から頂点 $1$ までの最短距離です。しかし、各 $i$ から個別に最短路を求めると時間がかかります。

そこで、すべての辺の向きを反転します。元のグラフにおける $i$ から $1$ への経路は、反転後のグラフにおける $1$ から $i$ への経路と一対一に対応し、コストも変わりません。

したがって、反転後のグラフで頂点 $1$ を始点としてダイクストラ法を行えば、頂点 $i$ までの最短距離として $C_i$ を求められます。

反転後の辺は、各 $x=1,2,\ldots,K$ について次のように追加できます。

• $y=\min(3x+1,K)$ とし、$y$ から $x$ へ、$x$ が奇数なら重み $1$、偶数なら重み $2$ の辺を張る。
• $y=\left\lceil x/2\right\rceil$ とし、$y$ から $x$ へ、$x$ が偶数なら重み $1$、奇数なら重み $2$ の辺を張る。

コストは操作前の値によって決まるため、どちらの場合も $x$ の偶奇を用いることに注意します。

最後に、各 $i=1,2,\ldots,N$ について $C_i$ を調べ、対応する $A_{C_i}$ を $1$ 増やします。

また、操作 $2$ だけを繰り返しても必ず $1$ に到達できます。$i\leq K\leq2^{18}$ なので、操作回数は高々 $18$ 回であり、各操作のコストは高々 $2$ です。したがって、すべての $i$ について $C_i\leq36$ が成り立ちます。

計算量は、ダイクストラ法を用いると $O(K\log K)$ です。