Union Find木を使って問題を解く②

Union Find木を使って問題を解く②

前前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

N匹の動物がいて、1,2、・・・・Nと番号がつけられています。

動物はすべて3つの種類A,B,Cのいずれかです。

AはBと食べ、BはCを食べ、CはAを食べます。

そして次の2種類の情報が順番に与えられます。

 ・タイプ1:xとyは同じ種類です。

 ・タイプ2:xはyを食べます。

これらの情報はすべて 正しいとは限りません。

以前に与えられた情報と 矛盾する情報 や、x、yが正しい番号でない ような
間違った情報が与えられる可能性があります。

与えられた情報のうち、間違った情報の個数 を出力してください。

また間違った情報は捨てると考えます。

[条件]

・動物数 は、1以上 50000以下

・与えられる情報の数は、0以上 100000以下

[解き方]
Union Find木 は、同じグループを管理するデータ構造ですが、この問題では同じ情報だけではなく 食べる という関係があります。

各動物について3つの要素 i-A、i-B、i-C をつくり、3×N個の要素で Union Find木 を作成し、次のように考えます。

  • i-xiが種類xである場合 を表す。
  • 各グループは、それらが すべて同時に起こる ことが分かっている。

例えば、i-Aj-B が同じグループである場合、iが種類Aならばjは必ず種類Bであり、jが種類Bならばiはかならず種類Aである ことを表します。

そうするとそれぞれの情報について、以下を行えばよいことになります。

  • タイプ1:xとyが同じ種類の場合
    x-Aとy-Ax-Bとy-Bx-Cとy-Cの3つのペアをグループ化する。
  • タイプ2:xがyを食べる場合
    x-Aとy-Bx-Bとy-Cx-Cとy-Aの3つのペアをグループ化する。

また、それぞれグループ化する前に 矛盾がおきているかどうか のチェックを行います。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#-------------入力---------------
n = 100 # 動物の数
# 2種類のタイプ情報、動物1、動物2
info_lst = [{'type':1, 'x':101, 'y':1},
{'type':2, 'x':1, 'y':2},
{'type':2, 'x':2, 'y':3},
{'type':2, 'x':3, 'y':3},
{'type':1, 'x':1, 'y':3},
{'type':2, 'x':3, 'y':1},
{'type':1, 'x':5, 'y':5}]
#--------------------------------
uf = UnionFind(n * 3)
ans = 0

for info in info_lst:
tp = info['type']
# [1 ~ n ]の範囲を、[0 ~ n - 1 ]の範囲にする
x, y = info['x'] - 1, info['y'] - 1

# 動物の番号の範囲をチェック
if x < 0 or x >= n or y < 0 or y >= n:
print('動物番号の範囲チェックエラー', info)
ans += 1
else:
if tp == 1: # 同じ種類の場合
if uf.same(x, y + n) or uf.same(x, y + n * 2):
print('矛盾', info)
ans += 1
else:
print('同じ種類としてグループ化', info)
uf.union(x, y)
uf.union(x + n, y + n)
uf.union(x + n * 2, y + n * 2)
else: # xはyを食べる場合
if uf.same(x, y) or uf.same(x, y + n * 2):
print('矛盾', info)
ans += 1
else:
print('食べられる種類としてグループ化', info)
uf.union(x, y + n)
uf.union(x + n, y + n * 2)
uf.union(x + n * 2, y)
print()
print('答え', ans)

[実行結果]

動物番号の範囲チェックエラー {'type': 1, 'x': 101, 'y': 1}

食べられる種類としてグループ化 {'type': 2, 'x': 1, 'y': 2}

食べられる種類としてグループ化 {'type': 2, 'x': 2, 'y': 3}

矛盾 {'type': 2, 'x': 3, 'y': 3}

矛盾 {'type': 1, 'x': 1, 'y': 3}

食べられる種類としてグループ化 {'type': 2, 'x': 3, 'y': 1}

同じ種類としてグループ化 {'type': 1, 'x': 5, 'y': 5}


答え 3

1つめの情報は 番号として間違っていて、4つめと5つめの情報は 矛盾している ので、正解は3 ということになります。