No.470

2-SAT 問題である.

まずは $N \gt 52$ のときは, 1文字になるのが文字の種類数を超えてしまい, 必ずかぶりが出るため, Impossible である.

$U_i$ を1文字, 2文字に切るのを true, 2文字1文字に切るのを false としてこれを $a_i$ とする.

$a_i, a_j$ は以下を満たさなければならない.

• $a_i = true, a_j = true$ としたときにかぶりがでるならば, $\overline{a_i} \lor \overline{b_i}$
• $a_i = true, a_j = false$ としたときにかぶりがでるならば, $\overline{a_i} \lor b_i$
• $a_i = false, a_j = true$ としたときにかぶりがでるならば, $a_i \lor \overline{b_i}$
• $a_i = false, a_j = false$ としたときにかぶりがでるならば, $a_i \lor b_i$

これらを満たす $a_i$ が存在するかどうかを調べればいい.