Anything Goes to One

2 secs 1024 MB
eSeF's icon eSeF

L=K+max(a)L=K+\max (a) とおきます。xx の値に対応する頂点 1, 2, ,L1,\ 2,\ \cdots ,L を考え、 操作を頂点間の移動と捉えれば頂点 11 から頂点 ii への最短経路長が求める答えとなります。

aia_i は全て相異なるため、 aiia_i\ge i と考えて良いです。従って辺の数は O(L1+L2++LN)=O(LlogN)O(\frac{L}{1}+\frac{L}{2}+\cdots +\frac{L}{N})=O(L\log N) となり、BFS などによって答えが求まります。

なお、操作途中に LL より大きい値を経由しないことは、操作2で割り算することに決めた場合に、商が最小となる頂点を目指しても損をしないことから言えます。