E - Swap or Reverse 解説
by 
toam
（考察パートについては tatyam さんのユーザー解説が分かりやすいので，そちらも合わせて参考にしてください．）
\((x,y)\in S\) のとき \((y,x)\in S\) とし，単に \((P_l,P_r)\in S\) のとき操作できるものとします．
ここで，\((x,y)\in S\) かつ \((y,z)\in S\) のとき，\((x,z)\) を \(S\) に追加しても問題ないことが分かります．
よって，\(S\) は無向グラフの辺の入力とみなすことができ，連結であるような二つの頂点 \((x,y)\) に対して操作を行う，と考えることができます．
すると，次のような方針を取ることができます．
- まず，reverse の操作によって，連結成分の列を決める．その後，swap によって前から順番に連結成分に含まれる頂点のうち小さいものを貪欲に割り当てていく．
reverse によってどのような連結成分の列が可能かを考えます．次の問題を考えます．
- 長さ \(N\) の整数列 \(X\) がある．\(X_l=X_r\) となる \((l,r)\) を選び \(X_l,\ldots,X_r\) を reverse するという操作を何回でも行えるとき，どのような \(X\) を作ることが可能か？
作ることが可能な列 \(Y\) の必要十分条件は以下です．（証明後述）
- 無向グラフ \(G\) を作る．\(i=1,2,\ldots,N-1\) に対して頂点 \(X_i\) と頂点 \(X_{i+1}\) の間に辺を追加する．このとき，
- \(Y_1=X_1\)
- \(Y\) は \(G\) のオイラー路の頂点番号を並べた列である．
元の問題に戻ります．まず，\(N\) 頂点のグラフ \(G_1\) を用意し，各 \(x,y\) に対して頂点 \(x\) と \(y\) の間に辺を追加します．\(G_1\) の連結成分数を \(K\) とし，連結成分に \(1\) から \(K\) までの番号を振ります． 次に，\(K\) 頂点のグラフ \(G_2\) を用意します．\(i=1,2,\ldots,N-1\) に対し，\(G_1\) において頂点 \(P_i,P_{i+1}\) がそれぞれ属する連結成分の番号を \(a,b\) として頂点 \(a,b\) の間に辺を追加します．
\(G_2\) 上でのオイラー路を構築しながら答えの順列 \(\mathrm{ans}\) を以下の手順で得ることができます．
- \(G_1\) において頂点 \(P_1\) が属する連結成分の番号を \(g\) とする．
- 以下を \(N\) 回繰り返す．
- \(G_1\) において，連結成分 \(g\) に属する頂点の番号のうち，まだ \(\mathrm{ans}\) に追加されていないものを \(\mathrm{ans}\) に追加する．
- \(G_2\) において \(g\) に隣接する頂点のうち，以下を満たすものを \(g'\) とする．
- 次に \(g'\) に進んでも \(G_2\) のオイラー路を構築することが可能である．
- そのようなものが複数ある場合，その中でまだ \(\mathrm{ans}\) に含まれていない最小の頂点番号を有する連結成分の番号を \(g'\) とする．
- \(g=g'\) とする．
これを愚直に実装すると \(O(N^2)\) になりますが，連結成分のサイズで平方分割することで \(O(N^{1.5})\) になります．\(O(N^{1.5}\log N)\) も定数倍が悪くなければ通ると思います．
実装が楽な平方分割の方針
\(G_2\) における隣接頂点を連想配列で管理します．各連結成分について，残っている最小の頂点を \(O(1)\) で取得できるようにしておきます．
- サイズが小さい連結成分：\(G_2\) の隣接頂点を全部みて，最も小さい頂点を有する連結成分を \(O(\sqrt{N})\) で取得します．
- サイズが大きい連結成分：各連結成分について，カウンター \(\mathrm{now}=1\) を用意しておきます．以下を繰り返します．
- もし 頂点 \(\mathrm{now}\) が使われておらず，かつ \(G_2\) において，今見ている連結成分に対応する頂点と頂点 \(\mathrm{now}\) を含む連結成分に対応する頂点の間に辺が残っていたら，次進むべき頂点は \(\mathrm{now}\) です．
- そうでない場合，\(\mathrm{now}\) をインクリメントして上の処理に戻ります，
- これらの処理は一つの大きい連結成分について全体で \(O(N)\) です．
次に進むべき頂点が決まったら，\(G_2\) の隣接頂点を管理する連想配列において，\(2\) つの連結成分が対応する頂点の間の辺を逐次削除します．
必要十分条件の証明
必要性
\(X\) から得られるグラフは，reverse の操作をしても不変です．よってグラフの形が不変量となり，\(Y\) から得られるグラフは \(X\) から得られるグラフと同じである必要があります．
十分性
帰納法で証明します．\(X_1=Y_1, X_2\neq Y_2\) を仮定します．\(X_2=Y_2\) とするのが目標です．同じグラフのオイラー路であることより，\((Y_1,Y_2)=(X_{i+1},X_i)\) または \((Y_1,Y_2)=(X_i,X_{i+1})\) を満たす \(i\) が存在します．
\((Y_1,Y_2)=(X_{i+1},X_i)\) を満たす \(i\) が存在する場合
\(X\) に対して \((l,r)=(1,i+1)\) と操作することで \(X_1=Y_1,X_2=Y_2\) となります．\((Y_1,Y_2)=(X_i,X_{i+1})\) を満たす \(i\) が存在する場合
\(X_L=X_R\) となる \(L\lt i+1\leq R\) が必ず存在します．そのような \(L,R\) に対して reverse 操作を行うことで 1 に帰着します．
実装例（Python）
from atcoder.dsu import DSU
from collections import defaultdict
import sys
sys.setrecursionlimit(3 * 10**5)
def solve():
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
uf = DSU(n)
for i in range(m):
x, y = map(lambda x: int(x) - 1, input().split())
uf.merge(x, y)
group = [uf.leader(i) for i in range(n)]
rem = [[] for i in range(n)]
G2 = [defaultdict(int) for i in range(n)]
for i in range(n - 1, -1, -1):
rem[group[i]].append(i)
if i != 0:
x, y = group[p[i - 1]], group[p[i]]
G2[x][y] += 1
G2[y][x] += 1
use = [0] * n
now = [0] * n
trail = []
def find(g):
if len(G2[g]) < 300:
mn = n
for u, c in G2[g].items():
if c > 0:
mn = min(mn, rem[u][-1])
return mn
while now[g] != n:
g2 = group[now[g]]
if use[now[g]] == 0 and g2 in G2[g] and G2[g][g2] > 0:
return now[g]
now[g] += 1
return n
def Eulerian(g):
tmp = rem[g].pop()
use[tmp] = 1
while True:
nxt = find(g)
if nxt == n:
break
ng = group[nxt]
G2[g][ng] -= 1
G2[ng][g] -= 1
Eulerian(ng)
trail.append(tmp)
Eulerian(group[p[0]])
print(*[i + 1 for i in trail[::-1]])
for _ in range(int(input())):
solve()
投稿日時:
最終更新: