#1067058 (C++17) No.5005 3-SAT

• 問題: No.5005 3-SAT
• ユーザー: ra5anchor
• 提出日時: 2025-04-14 00:59:53
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,902 ms / 2,000 ms
• コード長: 9,095 bytes
• コンパイル時間: 1,643 ms
• コンパイル使用メモリ: 122,236 KB
• 実行使用メモリ: 7,844 KB
• スコア: 98,857
• 最終ジャッジ日時: 2025-04-14 01:03:11
• 合計ジャッジ時間: 196,980 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	AC * 100

ソースコード

#include <iostream>
#include <vector>
#include <array>
#include <chrono>
#include <random>
#include <algorithm>
#include <string>

// 条件を表す構造体（a, b, c: 桁番号 / p, q, r: 必要な値）
struct Condition {
    int a, b, c, p, q, r;
};

// 時間計測クラス（開始時刻を保存し、指定の秒数を超えているか確認）
class TimeKeeper {
public:
    TimeKeeper() : start(std::chrono::steady_clock::now()) {}

    // LIMIT（秒）を超えているか
    bool is_time_over(double limit) {
        auto now = std::chrono::steady_clock::now();
        std::chrono::duration<double> elapsed = now - start;
        return elapsed.count() >= limit;
    }

    // 現在の経過時間（秒）を返す
    double time_now() {
        auto now = std::chrono::steady_clock::now();
        return std::chrono::duration<double>(now - start).count();
    }
private:
    std::chrono::steady_clock::time_point start;
};

// Solver クラス：局所探索を用いて解を改善する
class Solver {
public:
    int N; // 条件の数
    int K; // 桁数
    std::vector<Condition> X; // 条件リスト

    // 付属情報：各桁 k で、0/1 を選んだときに達成される条件番号リスト（Python 版では set を用いている）
    std::vector<std::array<std::vector<int>, 2>> C;

    // ビット操作の際に使うランダム順の桁番号リスト
    std::vector<int> indices;
    int idx_ptr;

    // 乱数生成器
    std::mt19937 rng;
    std::uniform_int_distribution<int> binary_dist;

    Solver(int N_, int K_, const std::vector<Condition>& X_)
        : N(N_), K(K_), X(X_), idx_ptr(0), rng(std::random_device{}()), binary_dist(0, 1)
    {
        // C の初期化：各桁について 0 と 1 の場合に達成される条件番号リストを作成
        C.resize(K);
        for (int k = 0; k < K; k++) {
            C[k][0].clear();
            C[k][1].clear();
        }
        for (int i = 0; i < N; i++) {
            const auto& cond = X[i];
            C[cond.a][cond.p].push_back(i);
            C[cond.b][cond.q].push_back(i);
            C[cond.c][cond.r].push_back(i);
        }
        // 事前に 0～K-1 の桁番号リストを作りランダムにシャッフル
        indices.resize(K);
        for (int i = 0; i < K; i++) {
            indices[i] = i;
        }
        std::shuffle(indices.begin(), indices.end(), rng);
    }

    // 条件を先頭から評価し、条件が満たされなくなった時点でループを抜ける（部分スコア評価）
    int calscore(const std::vector<int>& ans) {
        int sc = 0;
        for (int i = 0; i < N; i++) {
            const auto& cond = X[i];
            if (ans[cond.a] == cond.p || ans[cond.b] == cond.q || ans[cond.c] == cond.r) {
                sc++;
            } else {
                return sc;
            }
        }
        return sc;
    }

    // 全条件に対してスコアを計算する（全評価）
    int calscore_full(const std::vector<int>& ans) {
        int sc = 0;
        for (int i = 0; i < N; i++) {
            const auto& cond = X[i];
            if (ans[cond.a] == cond.p || ans[cond.b] == cond.q || ans[cond.c] == cond.r)
                sc++;
        }
        return sc;
    }

    // グリーディー法による初期解生成（各条件を順番にチェックして未定なら設定）
    std::pair<std::vector<int>, int> initial_solution() {
        std::vector<int> ans(K, -1);
        for (int i = 0; i < N; i++) {
            const auto& cond = X[i];
            if ( (ans[cond.a] == cond.p) || (ans[cond.b] == cond.q) || (ans[cond.c] == cond.r) )
                continue;
            if (ans[cond.a] == -1)
                ans[cond.a] = cond.p;
            else if (ans[cond.b] == -1)
                ans[cond.b] = cond.q;
            else if (ans[cond.c] == -1)
                ans[cond.c] = cond.r;
        }
        for (int k = 0; k < K; k++) {
            if (ans[k] == -1)
                ans[k] = binary_dist(rng);
        }
        int sc = calscore(ans);
        return {ans, sc};
    }

    // 別バリエーションの初期解生成：条件ごとに利用可能な候補からランダムに一つ選ぶ
    std::pair<std::vector<int>, int> initial_solution2() {
        std::vector<int> ans(K, -1);
        for (int i = 0; i < N; i++) {
            const auto& cond = X[i];
            if ( (ans[cond.a] == cond.p) || (ans[cond.b] == cond.q) || (ans[cond.c] == cond.r) )
                continue;
            std::vector<std::pair<int, int>> candidates;
            if (ans[cond.a] == -1)
                candidates.push_back({cond.a, cond.p});
            if (ans[cond.b] == -1)
                candidates.push_back({cond.b, cond.q});
            if (ans[cond.c] == -1)
                candidates.push_back({cond.c, cond.r});
            if (!candidates.empty()) {
                std::uniform_int_distribution<int> cand_dist(0, static_cast<int>(candidates.size() - 1));
                auto choice = candidates[cand_dist(rng)];
                ans[choice.first] = choice.second;
            }
        }
        for (int k = 0; k < K; k++) {
            if (ans[k] == -1)
                ans[k] = binary_dist(rng);
        }
        int sc = calscore(ans);
        return {ans, sc};
    }

    // 複数の初期解候補を生成し、最もスコアが高い解を選択する
    std::pair<std::vector<int>, int> multi_initial_solution(int num_candidates = 100) {
        std::vector<int> best_ans;
        int best_sc = -1;
        for (int i = 0; i < num_candidates; i++) {
            auto candidate = initial_solution2();
            if (candidate.second > best_sc) {
                best_ans = candidate.first;
                best_sc = candidate.second;
            }
        }
        return {best_ans, best_sc};
    }

    // 事前生成したランダムな桁番号リストから次の桁を取得（全体を使い切れば再シャッフル）
    int get_random_index() {
        if (idx_ptr >= K) {
            std::shuffle(indices.begin(), indices.end(), rng);
            idx_ptr = 0;
        }
        return indices[idx_ptr++];
    }

    // 局所探索：各ビット反転を試み、改善があれば更新するヒルクライミング法
    std::pair<std::vector<int>, int> solve(TimeKeeper &tk, double LIMIT) {
        // 初期解候補（候補数は 1 で十分）
        int n_iter = 1;
        auto init = multi_initial_solution(n_iter);
        std::vector<int> current_ans = init.first;
        int current_sc = init.second;
        std::vector<int> best_ans = current_ans;
        int best_sc = current_sc;
        int loop = 0;

        while (!tk.is_time_over(LIMIT)) {
            loop++;
            bool improved = false;
            // 全桁に対して反転を試みる
            for (int i = 0; i < K; i++) {
                int k = get_random_index();
                // ビット反転（in-place）
                current_ans[k] = 1 - current_ans[k];
                int new_sc = calscore(current_ans);
                int delta = new_sc - current_sc;
                if (delta >= 0) {
                    current_sc = new_sc;
                    if (current_sc > best_sc) {
                        std::cerr << "best: loop=" << loop << " current_sc=" << current_sc << "\n";
                        best_sc = current_sc;
                        best_ans = current_ans; // 解のコピー
                    }
                    improved = true;
                    break; // 1ビット反転で改善が見られた場合、次の外側ループへ
                } else {
                    // 改善がなければ反転を元に戻す
                    current_ans[k] = 1 - current_ans[k];
                }
            }
            if (!improved) {
                std::cerr << "not improved\n";
                break;
            }
        }
        return {best_ans, best_sc};
    }
};

int main(int argc, char* argv[]) {
    // コマンドライン引数に "--debug" があれば DEBUG モードとする
    bool DEBUG = false;
    for (int i = 1; i < argc; i++) {
        if (std::string(argv[i]) == "--debug") {
            DEBUG = true;
        }
    }
    
    // 時間計測用オブジェクトの生成
    TimeKeeper tk;
    double LIMIT = DEBUG ? 0.5 : 1.9;

    // 入力値：条件の数 2048, 桁数 256 として固定
    constexpr int N = 2048;
    constexpr int K = 256;
    std::vector<Condition> X;
    X.reserve(N);
    for (int i = 0; i < N; i++) {
        int a, b, c, p, q, r;
        std::cin >> a >> b >> c >> p >> q >> r;
        X.push_back({a, b, c, p, q, r});
    }

    // Solver の生成と解探索
    Solver solver(N, K, X);
    auto result = solver.solve(tk, LIMIT);
    std::vector<int> ans = result.first;
    int sc = solver.calscore(ans);

    // 出力：桁を逆順に結合して 1 行で出力
    for (int i = K - 1; i >= 0; i--) {
        std::cout << ans[i];
    }
    std::cout << "\n";

    std::cerr << "SC " << sc << "\n";
    return 0;
}