この解説は公式解説を私なりに再解釈したものであり、本質的に新しい情報はありません。

---

3
4 3
2 5
8 15

という入力を例に考えてみます。

2-SATへの帰着

「互いに素でない組が \(1\) つでもあったらダメ」と考え、ダメな条件を列挙することを考えてみます。上の例であれば問題は次のように読み替えられます。

問題：以下の条件に \(1\)つも該当しないような表裏の決め方は存在するか？

• \(1\) 枚目が表 かつ \(2\) 枚目が表
• \(1\) 枚目が表 かつ \(3\) 枚目が表
• \(1\) 枚目が裏 かつ \(3\) 枚目が裏
• \(2\) 枚目が表 かつ \(3\) 枚目が表
• \(2\) 枚目が裏 かつ \(3\) 枚目が裏

上で求めた条件を「これらに \(1\) つでも該当したらダメ」の形式ではなく、「これらを全て満たせばよい」の形式で書き直してみます。これは、全ての条件文の否定をとればよいです。

問題：以下の条件を全て満たすような表裏の決め方は存在するか？

• \(1\) 枚目が裏 または \(2\) 枚目が裏
• \(1\) 枚目が裏 または \(3\) 枚目が裏
• \(1\) 枚目が表 または \(3\) 枚目が表
• \(2\) 枚目が裏 または \(3\) 枚目が裏
• \(2\) 枚目が表 または \(3\) 枚目が表

ここで「\(i\) 番目のカードが表か？」を表す真偽値変数 \(X_i\) を考えます。するとこの問題は次のようになります。

問題：以下の論理式が真となるような \(X_i\) の真偽の決め方は存在するか？

\( (\lnot X_1 \lor \lnot X_2) \land (\lnot X_1 \lor \lnot X_3) \land ( X_1 \lor X_3) \land (\lnot X_2 \lor \lnot X_3) \land (X_2 \lor X_3)\)

これは 2-SATにほかならないので、この問題は2-SATの充足可能性を判定するアルゴリズムを用いて解けました……と言いたいところですが、このままでは節の数が最悪で \(O(N^2)\) となるため実行時間制限に間に合いません。（全てのカードの両面に \(2\) が書いてある場合など）

どうすれば節の数を減らすことができるでしょうか？

節の数を減らしたい

ABC177E『coprime』 を思い出してみましょう。この問題では「与えられた数について、どの \(2\) 数の組も互いに素か？」を判定するために、「同じ素因子を持つ数が \(2\) 度以上登場するか？」を調べました。今回の問題も同じようにして計算量を削減することができます。

素因数ごとに分け、「どの素数 \(p\) も、高々\(1\) 回しか現れない」という条件を考えます。冒頭の例であれば次のようになります。

問題：以下の条件を全て満たすような表裏の決め方は存在するか？

• 「\(1\) 枚目が表」「\(2\) 枚目が表」「\(3\) 枚目が表」のうち満たされるのは高々 \(1\) 個（素因子 \(2\) に関する条件）
• 「\(1\) 枚目が裏」「\(3\) 枚目が裏」のうち満たされるのは高々 \(1\) 個（素因子 \(3\) に関する条件）
• 「\(2\) 枚目が裏」「\(3\) 枚目が裏」のうち満たされるのは高々 \(1\) 個（素因子 \(5\) に関する条件）

これはそのままでは2-SATになりません。変形してみましょう。

2-SATへの帰着(2)

ここからしばらくは元の問題を離れて、「\(P_1,P_2,\ldots,P_n\) のうち真になるものは高々 \(1\) 個」という条件をいい感じの2-SATに落とし込むことを考えます。

例えば「どの \(2\) 個も同時に真になることはない」と考えることで \((\lnot P_1 \lor \lnot P_2) \land (\lnot P_1 \lor \lnot P_3)\land\ldots\) と書くことはできますが、これではやはり節の数が最悪 \(O(N^2)\) になってしまいます。

実は、累積和を用いるとうまくいきます！

\(P_1,P_2,\ldots,P_n\) の累積ORを \(Q_1,Q_2,\ldots,Q_n\) とします。より正確には

\( Q_i=\begin{cases} P_1 & i=1 \\ Q_{i-1} \lor P_i & i>1 \end{cases}\)

とします。このとき、「\(P_1,P_2,\ldots,P_n\) のうち真となるものが高々 \(1\) 個」であるためには

• 全ての \(i\) で「\(P_i\) が真ならば \(Q_i\) が真」が成り立つ
• 全ての \(i\) で「\(Q_{i-1}\) が真ならば \(Q_i\) が真」が成り立つ
• 全ての\(i\) で「\(P_i\) と \(Q_{i-1}\) が同時に真になることはない」が成り立つ

の \(3\) 条件を全て満たすことが必要十分です。ここから、「\(Q_i\) たちは \(P_i\) たちの累積ORである」という条件を外し、\(Q_i\) たちを単なる変数だと思い、「\(3\) 条件を全て満たすような \(P_i, Q_i\) への真偽値の割り当て」を考えてもなお成立します。（そうすると、「\(P_i\) は全て偽であるにも関わらず、\(Q_i\) が途中から真になる」というようなケースも含まれてしまいますが、「\(P_1,P_2,\ldots,P_n\) のうち真となるものが高々 \(1\) 個」の判定には影響しません）

(1つ目と2つ目の条件のイメージ図)

\(3\) 条件はいずれも \(n\) 個くらいの節によって記述できるため、「\(P_1,P_2,\ldots,P_n\) のうち真になるものは高々 \(1\) 個」という条件は、\(3n\) 個くらいの節を用いて記述できることがわかりました。

元の問題を解く

いま考えていた元の問題を再掲します。

問題：以下の条件を全て満たすような表裏の決め方は存在するか？

• 「\(1\) 枚目が表」「\(2\) 枚目が表」「\(3\) 枚目が表」のうち満たされるのは高々 \(1\) 個（素因子 \(2\) に関する条件）
• 「\(1\) 枚目が裏」「\(3\) 枚目が裏」のうち満たされるのは高々 \(1\) 個（素因子 \(3\) に関する条件）
• 「\(2\) 枚目が裏」「\(3\) 枚目が裏」のうち満たされるのは高々 \(1\) 個（素因子 \(5\) に関する条件）

これはぱっと見では2-SATになりませんが、実はいい感じの2-SATになることが前節の議論でわかりました。これで今度こそ実行時間に間に合うでしょうか？　計算量を考えてみます。

素因子 \(p\) に関する条件に関わるのは、\(p\) を素因子に持つような数が書かれている面だけです（例でいえば、素因子 \(2\) に関する条件に関わるのは、\(4\) が書かれた「\(1\) 枚目の表」、\(2\) が書かれた「\(2\) 枚目の表」、\(8\) が書かれた「\(3\) 枚目の表」の \(3\) つです）。「\(A_i,B_i\) たちのうち \(p\) を素因子に持つような数の個数」を \(N_p\) とします。前節の議論から、「～のうち高々 \(1\) 個が真」という条件は、登場する変数の \(3\) 倍くらいの個数の節で書けるのでした。つまり、素因子 \(p\) に関する条件は、\(3N_p\) くらいの個数の節で書くことができます。したがって、元の問題の条件は、これを全ての素数 \(p\) について考えることで \(\sum_p 3N_p\) くらいの個数の節で書けることがわかりました。さて、これはどのくらいのオーダーでしょうか？

「\(1\) 枚目が表」が関わってくるのは、\(1\) 枚目の表に書かれた数の素因子のみです。したがってそのようなものの個数は 高々\(O(\log A_1)\) 個です。他の場合も同様なので、\(A_i,B_i\) たちの最大値を \(M\) として、全体で \(O(N\log M)\) になることがわかりました。2-SATは節の数に対して線形のオーダーで解くことができるので、この問題も \(O(N\log M)\) で解けました。

実装例(C++ with ACL)