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が正しい番号でない ような間違った情報が与えられる可能性があります。 与えられた情報のうち、間違った情報の個数 を出力してください。 また間違った情報は捨てると考えます。
[条件]
・動物数Nは、1以上 50000以下 ・与えられる情報の数は、0以上 100000以下
[解き方]
Union Find木 は、同じグループを管理するデータ構造ですが、この問題では同じ情報だけではなく 食べる という関係があります。
各動物iについて3つの要素 i-A、i-B、i-C をつくり、3×Nこの要素で Union Find木 を作成し、次のように考えます。
- i-x は iが種類xである場合 を表す。
- 各グループは、それらがすべて同時に起こることが分かっている。
例えば、i-A と j-B が同じグループである場合、iが種類Aならばjは必ず種類Bであり、jが種類Bならばiはかならず種類Aであることを表します。
そうするとそれぞれの情報について、以下を行えばよいことになります。
- タイプ1:xとyが同じ種類の場合
x-Aとy-A、x-Bとy-B、x-Cとy-Cの3つのペアをグループ化する。 - タイプ2:xがyを食べる場合
x-Aとy-B、x-Bとy-C、x-Cとy-Aの3つのペアをグループ化する。
また、それぞれグループ化する前に矛盾がおきているかどうかのチェックを行います。
[Google Colaboratory]
1 | #-------------入力--------------- |
[実行結果]
動物番号の範囲チェックエラー {'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ということになります。