Namaran

Code daily. Without assist.

2026-10-06

assign.cpp

#include <vector>

using Clause = std::vector<int>;

std::vector<Clause> assign(const std::vector<Clause>& cnf, int lit) {
}

論理式はCNFで、std::vector<Clause> の各要素が節、節の中の整数がリテラルです。3 は変数 x3 を、-3 はその否定を表します。リテラル lit を真に決めたあとの式を返す assign を書いてください。lit を含む節は満たされたので取り除き、-lit は偽になったので各節から消します。節の順番と節の中のリテラルの順番は変えず、リテラルがすべて消えた節は空の節として残します。

入力例 1

assign({{1, 2}, {-1, 3}, {-2}}, 1)

出力例 1

{{3}, {-2}}

入力例 2

assign({{1, -2}, {2, 3}}, -2)

出力例 2

{{3}}

入力例 3

assign({{-1}, {2}}, 1)

出力例 3

{{}, {2}}
Reference
#include <algorithm>
#include <iterator>
#include <vector>

using Clause = std::vector<int>;

std::vector<Clause> assign(const std::vector<Clause>& cnf, int lit) {
    std::vector<Clause> out;
    for (const auto& clause : cnf) {
        if (std::ranges::contains(clause, lit)) continue;
        Clause rest;
        std::ranges::remove_copy(clause, std::back_inserter(rest), -lit);
        out.push_back(rest);
    }
    return out;
}

参考実装は節ごとに2通りに分けます。lit を含む節は std::ranges::contains で見つけて飛ばし、それ以外の節は std::ranges::remove_copy で -lit だけを除いて写します。入力例3では、{-1} から -1 を除くと何も残らず、空の節 {} になります。空の節はどんな割り当てでも満たせないので、ソルバはこれを見て、lit を真にした選択が矛盾したと判断できます。

掲載したのは参考実装で、唯一の正解ではありません。std::ranges::contains は C++23 で加わった関数で、それより前の規格では std::ranges::find(clause, lit) != clause.end() と書きます。