Codeforces Round #614 (Div. 1) D. Chaotic V.
個人的に超好きな問題 この難易度帯自力ACできたのはかなり嬉しい
問題
無限の頂点を持つグラフが存在し、頂点に1から番号がふられている。2以上の頂点は
の素因数のうち最も小さい値を
とし
と辺で繋がっている。このグラフ上に
個のパーツが置かれており、
番目のパーツは頂点
に置かれている。グラフ上の頂点を一点選びすべてのパーツとの距離の総和をとるとき、総和としてあり得る値のうち最小値を答えよ。
制約
解法
まずは適当に頂点を一つ選んだとして、選んだ頂点をどのように動かしていくことで距離の総和を最小化できるかを考える。与えられるグラフは自明に木なので、選んだ頂点を動かす方向にパーツのうち過半数が存在すれば距離の総和が小さくなることがわかる。よって、過半数のパーツが存在する方向に選ぶ頂点を動かし続け、どの方向にも過半数のパーツが存在しなくなるまでこれを繰り返せばよい。最初に選ぶ頂点は1とする。
次にこの木の構造を考察する。1を根とする根つき木として考えるとすべての頂点は自身の番号の素因数のうち最小のもの以下の全ての素数をそれぞれ掛け合わせた番号の頂点と繋がっていることがわかる。下の図は5までの素数が存在しない場合だがおおよそこのようなイメージであることがわかる。
ここで子に移動していく操作は素数をかける操作と捉えることができる。さらに重要な考察として、子に移動していく場合かける素数の値は広義単調減少となる。
パーツが置かれている頂点について、を素因数分解した値は
から
までを素因数分解して累積和をとれば求めることができる。登場する素数の最大値は当然
以下となる。よって
以下の素数について降順に
個のパーツのうち過半数が素因数としてその素数を持っているかどうかを調べ、持っていればその方向に下るということを繰り返せばよい。また
の持つ素因数の数はそれぞれの素数について広義単調増加であるため
の値でソートしておくことで下っている方向に存在するパーツを区間として持つことができる。
