Namaran

Code daily. Without assist.

2026-08-29

satisfies.cpp

bool satisfies(const std::vector<std::vector<int>>& cnf, const std::vector<bool>& value) {
}

変数 x1, x2, … の論理式を、節の並び cnf で表します。節は整数の並びで、正の整数 k は「xk が真」、負の整数 -k は「xk が偽」を表し、節は並んだ条件の少なくとも1つが成り立つときに真です。論理式は、すべての節が真のときに真です。xk の値が value[k - 1] のとき、論理式が真かどうかを返す satisfies を書いてください。条件を1つも持たない空の節は偽、節を1つも持たない cnf は真とします。

入力例 1

satisfies({{1, -2}, {2, 3}}, {true, false, true})

出力例 1

true

入力例 2

satisfies({{1, -2}, {2, 3}}, {false, true, false})

出力例 2

false

入力例 3

satisfies({}, {})

出力例 3

true
Reference
bool satisfies(const std::vector<std::vector<int>>& cnf, const std::vector<bool>& value) {
    return std::ranges::all_of(cnf, [&](const std::vector<int>& clause) {
        return std::ranges::any_of(clause,
                                   [&](int lit) { return value[std::abs(lit) - 1] == (lit > 0); });
    });
}

「すべての節が真」を std::ranges::all_of で、「節の中の少なくとも1つが成り立つ」を std::ranges::any_of で書きます。1つの条件 lit が成り立つのは、lit の絶対値が指す変数の値 value[std::abs(lit) - 1] が、lit が正なら真、負なら偽のときで、これを (lit > 0) との比較1つで表しています。

入力例 2 では、x1 が偽、x2 が真なので、1つ目の節 {1, -2} の条件はどちらも成り立たず、2つ目の節を見るまでもなく偽です。空の範囲に対して any_of は false、all_of は true を返すので、空の節は偽、入力例 3 の空の cnf は真になり、決まりどおりの値が特別扱いなしで出ます。

掲載したのは参考実装で、唯一の正解ではありません。範囲 for を2重に回し、成り立つ条件が見つかった節は次の節へ進み、どの条件も成り立たない節が見つかった時点で false を返す書き方でも同じ結果になります。