第11回の過去問題全部

第11回

第11回 D問題似ている文字列(7点) 解答例

問題

D - 似ている文字列

私の言語

Python (3.8.2)

前提

まず公式解説を読まずに解きました。
解いた後に公式解説を読んで「Union-Findのコードがあれば速攻でできる」と知りました。ブランクのせいかまったく思いつかなかった。

なので今回は解答例として二つ記載しておきます。一つがUnion-Findを使ったものでもう一つがUnion-Findを使っていないものです。

Union-Find使用版

Union-Findについて詳しくは検索していただければいくらでも情報出てくるかと思いますが、要は値のグルーピングを木構造で行うというものです。

下記はUnion-Findのクラスです。今回の問題で最低限必要な内容だけを書いています。競技プログラミングで常に使うならもっと扱いやすいように機能追加した方が良いです。

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n  # 親要素

    # 根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x  # 自分が根である
        else:
            self.parents[x] = self.find(self.parents[x])  # 親の値を根の値で置き換える
            return self.parents[x]
            
    # 根が違ったら結合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        self.parents[x] = y

最初に要素数分の配列を用意しています（初期値-1）。
そして、unionメソッドが呼び出される度に、引数として渡された二つの要素を繋げています。
原理自体は非常にシンプルです。

このクラスを使って実際に今回の問題を解くと以下の通りです。

N = int(input())
uf = UnionFind(26)  # アルファベット数で初期化する

for i in range(N):
    a, b = input().split()
    uf.union(ord(a) - ord('a'), ord(b) - ord('a'))  # アルファベットを数値化して結合

S = input()
T = input()

# 文字列の各文字が同じグループかを判定している。
for i in range(len(S)):
    if uf.find(ord(S[i]) - ord('a')) != uf.find(ord(T[i]) - ord('a')):
        print("No")
        exit()
print("Yes")

Union-Find不使用版

N = int(input())

# aからzの26個のkeyを持つ辞書を生成。valueはkey同様
az = {}
for i in range(ord('a'), ord('z') + 1):
    az[chr(i)] = chr(i)

# 似ている文字同士は同じ文字で置換してしまう。
# 置換後の文字を大文字、置換前の文字を小文字として区別する
for i in range(N):
    a, b = input().split()

    if az[a].isupper() and az[b].isupper():  # aとbの両方が置換済み
        # az[b]と同一の値をaz[a]で置換してしまう。つまりaかbと似た文字はすべて同じ文字となる
        tmp = az[b]
        for j in range(ord('a'), ord('z') + 1):
            if az[chr(j)] == tmp:
                az[chr(j)] = az[a]
    elif az[a].isupper():  # aだけが置換済み
        az[b] = az[a]
    elif az[b].isupper():  # bだけが置換済み
        az[a] = az[b]
    else:  # aもbも小文字
        az[a] = az[b] = az[a].upper()

S = input()
T = input()

new_s = new_t = ""
for i in range(0, len(S)):
    new_s += az[S[i]]
    new_t += az[T[i]]

if new_s == new_t:
    print("Yes")
else:
    print("No")

まずazという辞書を用意します。
中身は下記のように、ただ'a':'a' , 'b','b' , ... 'z':'z'というだけのものです。

{'a': 'a', 'b': 'b', 'c': 'c', 'd': 'd', 'e': 'e', 'f': 'f', 'g': 'g', 'h': 'h', 'i': 'i', 'j': 'j', 'k': 'k', 'l': 'l', 'm': 'm', 'n': 'n', 'o': 'o', 'p': 'p', 'q': 'q', 'r': 'r', 's': 's', 't': 't', 'u': 'u', 'v': 'v', 'w': 'w', 'x': 'x', 'y': 'y', 'z': 'z'}

これに対し、入力で似た文字とされたkey値が持つvalueを同じ文字に変更していきます。
たとえば渡された文字が'a'と'z'なら、az['a']とaz['z']のvalueを同じ文字にする。
この同じ文字は他と区別がつくなら何でも良いです。

これを繰り返すと、似た文字同士はすべて同じ文字となり、似た文字として指定されなかったアルファベットは最初のままです。

最後に入力Sと入力Tに登場する文字をazのvalueで置換し、置換後の文字列同士を比較すれば完了です。

最後に宣伝

SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社採用サイトよりご確認ください。

是非ともよろしくお願いいたします。