[AtCoder] ABC 126 E – 1 or 2

2019年5月20日

問題

方針

与えられた情報から番号を当てられるか？

\( A_{X_i} + A_{Y_i} + Z_{i}\) が偶数という情報から番号を当てられることができるかを考えます。

例えば、\( A_1 + A_2 + 3 \mod 2 = 0 \) という情報から、\( (A_1, A_2) = (1, 2), (2, 1) \) ということが分かります。次に、\( A_1 + A_2 + 2 \mod 2 = 0 \) という情報から、\( (A_1, A_2) = (1, 1), (2, 2) \) ということが分かります。これは、\( Z_i \) が偶数か奇数かどうかで得られる情報が変わるということです。

ここで \( A_1 \) について考えます。\( A_1 + A_2 + 3 \mod 2 = 0 \) のとき、\( A_1 + A_3 + 2 \mod 4 = 0 \) や \( A_1 + A_3 + 5 \mod 2 = 0 \) ということが分かったとしても、上記より、\( A_1 \) について分かることは \( 1 \) か \( 2 \) の値を取るということしか分かりません。よって、\(Z_i \) の値は関係ないことが分かります。

カードをめくることで得られる情報

上記の考察から、片方の数字が分かればもう片方の数字が確定することが言えます。これは、\( (A_1, A_2) = (1, 2), (2, 1) \) または、\( (A_1, A_2) = (1, 1), (2, 2) \) という情報から分かります。

次に、\( (A_1, A_2) \), \( (A_1, A_3) \) という情報が与えられたとき、どれか一つが分かれば、残りの二つをカードをめくらずに当てることができます。このことを考えると、同じグループに属するカードは、そのグループのどれか一つのカードをめくれば残りが分かるということが推測できます。このようなグループの数は、Union Find で求めることができます。グループの数だけカードをめくることですべてのカードを当てることができます。

コード

提出したコード