Codeforces #403 (Div. 2) D: Innokenty and a Football League

解法

各チームについてshort nameの付け方は2通りある。

また、それぞれのチームのshort nameの関係は、いくつかの包含関係で表せる。

2値変数Aが真であることをa、偽であることを¬aのように表すと

(x[1]=>x[2])∧(x[2]=>x[3])∧(x[3]=>x[1])∧(¬x[3]=>x[2])∧(¬x[1]=>¬x[2])∧(¬x[2]=>¬x[1])

のような複数の包含関係を「かつ」でつないだような論理式全体を真にするような各変数の値の割り当てはImplication graphの強連結成分分解で知ることができる。Implication graphはa=>bのような包含関係をそのまま有向辺として持つグラフのこと。各強連結成分の真偽値が等しくなるような2値の割り当てが解になる。ただし、aと¬aの連結成分が等しい場合、aと¬aの値が等しいことになり明らかに矛盾。この時は解なし。また、対偶関係も辺として加えられるので注意。

これを実際の問題に当てはめてみよう。

(1)異なるチームS,TについてSの名付け方sとTの名付け方¬tが等しい場合

チーム名の重複は許されないから

s=>t

かつ

¬t=>¬s

この2条件は対偶関係になっている。

(2)名付け方sと名付け方tが等しい場合

つまり、問題文で与えられているように

Sの名付け方が(DIN, DIB), Tの名付け方が(DIN, HOGE)

のような場合

SをDIBと名付けた場合はTはDINとは名付けられないのであった。

よって

¬s=>¬t

同様に

¬t=>¬s

これらに対偶関係を加えてまとめると

¬s<=>¬t

かつ

s<=>t

思いつき方

知識