Namaran

Code daily. Without assist.

2026-08-29

fewest_true.cpp

#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    auto formula = [](const std::vector<bool>& x) {
        return !x[0] && (x[1] || x[2]);
    };
    for (int k = 0; k <= 3; ++k) {
        std::vector<bool> x(3);
        std::fill(x.begin(), x.begin() + k, true);
        do {
            if (formula(x)) {
                std::printf("%d%d%d\n", int(x[0]), int(x[1]), int(x[2]));
                return 0;
            }
        } while (std::next_permutation(x.begin(), x.end()));
    }
    std::puts("UNSAT");
}

3つの変数 x[0]、x[1]、x[2] の真偽の割り当てのうち、formula を満たし、真にする変数の個数が最も少ないものを探して 0 と 1 の並びで出力し、1つも無ければ UNSAT と出力するプログラムです。真の個数 k を0から順に増やし、k ごとに真偽の並べ方をすべて試すつもりです。この formula は x[0] が偽で x[2] だけが真の割り当てで満たせるので、本来は 001 と出力されるはずが、いまは UNSAT と出力されます。

Answer

Wrong

std::vector<bool> x(3);
std::fill(x.begin(), x.begin() + k, true);
} while (std::next_permutation(x.begin(), x.end()));

std::next_permutation は、並びを辞書順で次のものに並べ替えて true を返し、すでに辞書順で最後の並びなら最初の並びに戻して false を返します。bool では false が true より小さいので、辞書順で最初の並びは真を後ろに寄せた {false, false, true}、最後の並びは真を前に寄せた {true, false, false} です。

std::fill は先頭から k 個を真にするので、どの k でも x は最初から辞書順で最後の並びになっています。そのため do の本体は1回だけ回り、next_permutation が false を返してループを抜けます。試されるのは 000、100、110、111 の4通りだけで、k が1以上のときはどれも x[0] が真なので formula を満たさず、UNSAT に着きます。

Right

std::vector<bool> x(3);
std::fill(x.end() - k, x.end(), true);
} while (std::next_permutation(x.begin(), x.end()));

末尾の k 個を真にすると、x は辞書順で最初の並びから始まります。next_permutation はそこから最後の並びまで1つずつ進むので、真が k 個の並べ方をすべて試してから false を返します。k が1のとき最初に試すのが 001 で、これが formula を満たして出力されます。先頭から埋めたあとで std::ranges::sort(x) を呼んでも、同じく最初の並びから始められます。