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() と書きます。