Supershipの名畑です。
前回の記事「アルゴリズム実技検定(PAST)について 並びに 第11回A〜C問題 Python解答例」の続きです。
アルゴリズム実技検定(PAST)第11回のD問題の私の解答例(Python3)を公開します。
私が解いた感覚だと、D問題〜F問題(7点問題)でABC(AtCoder Beginner Contest)のB問題とC問題の間ぐらいの難易度でしょうか。
未読の方は「採用活動のために競技プログラミング（AtCoder）を始めて一年経ったので感想を書きます」も一緒に読んでいただけると嬉しいです!
第11回の過去問題全部
第11回 D問題 似ている文字列(7点) 解答例
問題
私の言語
- 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株式会社 採用サイトよりご確認ください。
是非ともよろしくお願いいたします。