Official

E - Sliding Puzzle On Tree Editorial by maspy

ヒント → https://atcoder.jp/contests/agc066/editorial/9634

本解説において，石は \(a, b\) 等の文字で表し，頂点は \(u, v\) 等の文字で表します．

[1] ひとつの石の存在範囲

まずは \(K\) を固定して考えます．

ひとつの石がどの頂点に移動できるかを考えてみます．石 \(a\) の存在できる頂点全体の集合を \(S(a)\) と書くことにします．

ひとつの石の存在範囲を調べることは，\(O(NK)\) 状態の適当な探索アルゴリズムで可能です．最後にスワップした辺はどれであるか，その辺の両側にいくつずつの他の石があるのかという情報を状態とすればよいです．

この計算がどのようなものかを考えると，次数 \(3\) 以上の頂点に注目した以下のことが分かります．

  • \(u\) を次数 \(3\) 以上の頂点だとする．\(S(a)\) が\(u\) の近傍を \(2\) 点以上含むならば，\(S(a)\) は \(u\) の近傍をすべて含む．以下これが成り立つとき，石 \(a\) は頂点 \(u\) を利用可能であるということにする．
  • 石 \(a, b\) (\(a\neq b\)) が同じ次数 \(3\) 以上の頂点 \(u\) を利用可能であるとき，\(S(a)=S(b)\) が成り立つ．
  • 逆に石 \(a,b\) (\(a\neq b\)) について \(S(a)=S(b)\) であるとき，これらは同じ次数 \(3\) 以上の頂点 \(u\) を利用可能である．

\(2\) 番目の性質は，次数 \(3\) 以上の頂点のまわりで各部分木ごとの石の個数を自由に調整できるというようなことから分かります．\(3\) 番目の性質は \(a,b\) どちらかが次数 \(3\) 以上の頂点を利用可能できる場合には明らかで，そうでない場合にはその石の各方向にある石の個数が不変となることから分かります．

[2] 答えの計算（\(K\) が固定された場合）

次が成り立ちます：石 \(a, b\) に対して \(S(a)=S(b)\) が成り立つとき，\(a,b\) のみをスワップすることが可能である．つまり任意の石の配置からそのうち石 \(a,b\) の位置だけを入れ替えた配置を得ることが可能である．

このことを確認します．\(S(a)=S(b)\) が成り立つとき，\(a, b\) どちらもがある次数 \(3\) 以上の頂点 \(u\) を利用可能なのでした．よって次のような手順により目標を達成できます．

  • (1) まず石 \(a\) を \(u\) の近傍に移動させ，\(u\) およびそのある近傍に石がない状態にできます．必要があれば最後に数回動かして，\(a\) が \(u\) から見て \(b\) と異なる部分木にあるようにしておきます．

  • (2) さらに石 \(b\) も \(u\) を利用可能なので，この状態から \(b\) を \(u\) の隣まで移動させて，\(b\) から見て \(u\) 側に部分木内に石のない頂点が \(2\) 個以上あるようにできます．この操作過程において，\(b\) を動かす辺の両側にある石の個数がいくつかだけが重要だったので，石 \(a\) の位置を変えないままこのことを達成することができることが分かります．

  • (3) \(u\) およびその近傍のひとつには石がなく，石 \(a,b\) が \(u\) の近傍にある状態になりました．ここから適切に \(6\) 回操作すると，石 \(a,b\) だけの位置をスワップすることができます．

  • (4) (2) の操作を逆順に行います．

  • (5) (1) の操作を逆順に行います．

石が置かれている頂点全体の集合を固定したときに，何通りの石の配置がありうるかを考えてみましょう．そのような配置を \(2\) つとり，一方ではある頂点に石 \(a\) が，もう一方では同じ頂点に石 \(b\) が置かれているならば，\(S(a)=S(b)\) が成り立つことは明らかです．逆に \(S(a)=S(b)\) が成り立つような \(2\) つの石は自由にスワップできるのでした．

したがって，石が置かれている頂点全体の集合を固定したときには，答は次のように求められることが分かります：

  • 石全体を，\(S(a)\) が等しいような石からなる集合に分割する．大きさ \(n_1, n_2, n_3, \ldots\) の集合に分割されるならば，ありうる石の配置は \((n_1!)(n_2!)\cdots\) 通りである．

石が置かれている頂点全体の集合を固定していたことを考えると，この値に \(\binom{N}{K}\) をかけたものが問題の答になります．

\(S(a)=S(b)\) という関係で石を分類しましょう． \(S(a)\) が，\(a\) が利用可能であるような次数 \(3\) 以上の頂点のひとつから決まることを思い出すと，これは次のようなグラフの連結成分分解に帰着されます．

  • 木の頂点を表す \(N\) 個の頂点と，石を表す \(K\) 個の頂点を用意する．
  • 石 \(a\) に対して \(a\) が利用可能な次数 \(3\) 以上の頂点 \(u\) が存在するならば，そのような \(u\) をひとつとり \(a\) と \(u\) の間に辺を張る．
  • 次数 \(3\) 以上の頂点 \(u,v\) に対し，ある石が \(u\) を利用できるならば \(v\) も利用できるときに \(u, v\) の間に辺を張る．

石から次数 \(3\) 以上の頂点の間に張る辺については，その接続先を，その石からある方向に最も近い高々 \(2\) 頂点に限定することが可能です．次数 \(3\) 以上の頂点 \(u, v\) の間に張る辺については，その \(2\) 頂点間を結ぶパス上に他の次数 \(3\) 以上の頂点が存在しないような組 \(O(N)\) 個に限定することが可能です．したがって，\(O(N)\) 通りの対に対して辺を張れるかを調べることになります．

石と頂点の間に辺が張られるかは，石からある部分木方向にある石のないマスの個数と，石と頂点の距離によって決めることができます．次数 \(3\) 以上の頂点の間に辺が張られるかはその \(2\) 頂点間の距離によって決めることができます．

以上を適切に実装すれば，固定された \(K\) に対する答を計算することができます．

[3] 答えの計算（すべての \(K\) に対して計算する）

個々の \(K\) に対する答が正しく計算できるようになれば，それをすべての \(K\) に対する計算にするのはそれほど難しくありません．

\(K = N, N-1, \ldots, 1\) の順に計算することにすると，石と頂点からなるグラフに対して辺を追加していきながら連結成分を管理するというタイプの計算ができればよいということになります．石は減らす必要がありますが，これはグラフの連結性を変えないまま連結成分内の石の個数を変えればよく，必要な計算はすべて UnionFind のデータ構造を用いて行えます．

石の初期配置は自由に選べるので，例えば preorder の大きい方から配置することを考えると実装が簡潔になると思います．UnionFind を用いる部分以外の計算はすべて \(O(N)\) 時間でできて，全体で \(O(N\alpha(N))\) 時間で解くことができます．

posted:
last update: