AtCoder Beginner Contest 399 E - Replace

導入

atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。

使用しているアルゴリズム

• Union-Find

解法のポイント

この問題では、S から T への変換に必要な「最小の置換回数」を求めます。
制約の中で重要なのは、置換の過程において循環があった場合に余計な1手が必要になる点です。

解法の流れは以下の通りです：

1. 変換関数 A を構築

   • S[i] -> T[i] に従って A[ord(S[i]) - ord('a')] = ord(T[i]) - ord('a') を構築。
   • 一貫しない変換（すでに登録されてるのに違う変換先が出てくる）は -1 を出力。

2. トリビアルな条件処理

   • S == T の場合は置換不要なので 0。
   • A が [0, 1, ..., 25] の場合置換不可能なため -1。

3. 置換回数のカウント

   • A[i] != -1 で i != A[i] の場合に置換が必要なのでカウント。
   • 同時に UnionFind によって変換グループを構築（無向グラフで連結成分を作る）。
   • ある連結成分において、全ノードが変換先として使われている場合（in_digが全て1）、
     変換のサイクルがあると判断して、追加で1手必要。

4. UnionFind のグルーピング

   • 変換関係が閉じたサイクルになっている場合は、変換に余分な一手が必要（例：a→b→c→a など）。

全体的に、UnionFind で変換の「連結成分」を検出しつつ、変換に必要なステップ数を数えていくアプローチです。

ACサンプル

class UnionFind:
  def __init__(self,n):
    self.parent = [i for i in range(n)]
  
  def find(self,x):
    if self.parent[x] != x:
      self.parent[x] = self.find(self.parent[x])
    return self.parent[x]
  
  def merge(self,x,y):
    x_root = self.find(x)
    y_root = self.find(y)
    if x_root != y_root:
      self.parent[x_root] = y_root
  
  def groups(self):
    from collections import defaultdict
    r = defaultdict(list)
    for i,p in enumerate(self.parent):
      r[self.find(p)].append(i)
    
    return r.values()

C = 26
N = int(input())
S = input()
T = input()
A = [-1] * C

if S == T:
  print(0)
  exit()

for i in range(N):
  a = ord(S[i]) - ord("a")
  b = ord(T[i]) - ord("a")
  if A[a] != -1 and A[a] != b:
    print(-1)
    exit()
  A[a] = b

if sorted(A) == [i for i in range(26)]:
  print(-1)
  exit()

in_dig = [0] * C
uf = UnionFind(C)
ct = 0

for i,x in enumerate(A):
  if x != -1:
    in_dig[x] = 1
    uf.merge(i,x)
    if x != i:
      ct += 1

for vs in uf.groups():
  if len(vs) > 1:
    if all(in_dig[v] == 1 for v in vs):
      ct += 1

print(ct)

リンク

ACサンプル集(アルゴリズム逆引き)

問題へのリンク