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

• 問題: No.5005 3-SAT
• ユーザー: ra5anchor
• 提出日時: 2025-04-14 02:02:47
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,903 ms / 2,000 ms
• コード長: 9,170 bytes
• コンパイル時間: 1,939 ms
• コンパイル使用メモリ: 127,008 KB
• 実行使用メモリ: 7,848 KB
• スコア: 98,923
• 最終ジャッジ日時: 2025-04-14 02:06:06
• 合計ジャッジ時間: 198,572 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

ソースコード

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

using namespace std;
using namespace std::chrono;

// 条件1件分の情報を保持する構造体
struct Condition {
    int a, b, c, p, q, r;
};

// 時間計測用クラス
class TimeKeeper {
    steady_clock::time_point start_time;
public:
    TimeKeeper() {
        start_time = steady_clock::now();
    }
    // LIMIT（秒）を経過しているかどうか
    bool is_time_over(double limit) {
        auto now = steady_clock::now();
        double elapsed = duration_cast<duration<double>>(now - start_time).count();
        return elapsed >= limit;
    }
    double time_now() {
        auto now = steady_clock::now();
        return duration_cast<duration<double>>(now - start_time).count();
    }
};

// Solver クラス（問題の解法を担当）
class Solver {
public:
    int N, K;                   // 条件数とビット数
    vector<Condition> X;        // 条件リスト
    // C[k][0/1]：k 桁目が 0/1 になった場合に影響を受ける条件のインデックスリスト
    vector< array<vector<int>, 2> > C;
    vector<int> indices;        // ビットのランダム順序
    int idx_ptr;                // インデックスリストのポインタ
    vector<bool> satisfied;     // 各条件の成立状況
    mt19937 rng;                // 乱数生成器

    Solver(int N_, int K_, const vector<Condition>& X_) : N(N_), K(K_), X(X_), C(K), idx_ptr(0), satisfied(N, false) {
        random_device rd;
        rng = mt19937(rd());
        // 各ビット位置に対して、影響を受ける条件のインデックスを登録
        for (int i = 0; i < N; i++) {
            int a = X[i].a, b = X[i].b, c = X[i].c;
            int p = X[i].p, q = X[i].q, r = X[i].r;
            // 各ビット位置のインデックスが範囲内なら追加
            if(a >= 0 && a < K) C[a][p].push_back(i);
            if(b >= 0 && b < K) C[b][q].push_back(i);
            if(c >= 0 && c < K) C[c][r].push_back(i);
        }
        // 0～K-1 のインデックスを生成しランダムシャッフル
        indices.resize(K);
        for (int i = 0; i < K; i++) {
            indices[i] = i;
        }
        shuffle(indices.begin(), indices.end(), rng);
    }

    // 初期解 ans に対して各条件が成立しているかを計算
    void initialize_satisfied(const vector<int>& ans) {
        for (int i = 0; i < N; i++) {
            const Condition& cond = X[i];
            satisfied[i] = (ans[cond.a] == cond.p || ans[cond.b] == cond.q || ans[cond.c] == cond.r);
        }
    }

    // 先頭から連続して成立している条件数を返す（start からチェック開始）
    int calc_prefix_score(int start = 0) {
        int sc = start;
        while (sc < N && satisfied[sc])
            sc++;
        return sc;
    }

    // 全条件に対して先頭から条件成立している連続個数を計算
    int calscore(const vector<int>& ans) {
        int sc = 0;
        for (int i = 0; i < N; i++) {
            const Condition& cond = X[i];
            if (ans[cond.a] == cond.p || ans[cond.b] == cond.q || ans[cond.c] == cond.r)
                sc++;
            else
                break;
        }
        return sc;
    }

    // グリーディー法により初期解を生成する
    pair<vector<int>, int> initial_solution() {
        vector<int> ans(K, -1);
        for (int i = 0; i < N; i++) {
            const Condition& 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;
        }
        uniform_int_distribution<int> bit_dist(0, 1);
        for (int k = 0; k < K; k++) {
            if (ans[k] == -1)
                ans[k] = bit_dist(rng);
        }
        int sc = calscore(ans);
        return make_pair(ans, sc);
    }

    // シャッフルされた indices からランダムに1要素を返す
    int get_random_index() {
        if (idx_ptr >= K) {
            shuffle(indices.begin(), indices.end(), rng);
            idx_ptr = 0;
        }
        return indices[idx_ptr++];
    }

    // 山登り法による局所探索
    pair<vector<int>, int> solve(TimeKeeper& tk, double LIMIT) {
        auto init = initial_solution();
        vector<int> current_ans = init.first;
        int current_sc = init.second;
        initialize_satisfied(current_ans);
        vector<int> best_ans = current_ans;
        int best_sc = current_sc;
        int loop = 0;
        while (!tk.is_time_over(LIMIT)) {
            loop++;
            bool improved = false;
            // K ビット全てについて反転を試行
            for (int i = 0; i < K; i++) {
                int k = get_random_index();
                int old_val = current_ans[k];
                int new_val = 1 - old_val;
                current_ans[k] = new_val;
                // k 番目のビットに関係する条件を取得（C[k][0] と C[k][1] の和集合）
                vector<int> affected;
                for (int cond_idx : C[k][0]) {
                    affected.push_back(cond_idx);
                }
                for (int cond_idx : C[k][1]) {
                    affected.push_back(cond_idx);
                }
                // 重複条件の除去（必要な場合のみ）
                sort(affected.begin(), affected.end());
                affected.erase(unique(affected.begin(), affected.end()), affected.end());

                // ロールバック用に古い条件の成立状態を保存
                vector<bool> old_sat(affected.size());
                for (size_t j = 0; j < affected.size(); j++) {
                    old_sat[j] = satisfied[affected[j]];
                }
                // 影響を受けた条件のみ再評価
                for (int cond_idx : affected) {
                    const Condition& cond = X[cond_idx];
                    satisfied[cond_idx] = (current_ans[cond.a] == cond.p ||
                                           current_ans[cond.b] == cond.q ||
                                           current_ans[cond.c] == cond.r);
                }
                // 反転前のスコアは先頭から current_sc 番目まで成立しているはず
                // 影響を受けた条件の中で一番小さい番号と current_sc の小さい方から再評価
                int candidate = current_sc;
                if (!affected.empty()) {
                    int min_affected = *min_element(affected.begin(), affected.end());
                    candidate = min(current_sc, min_affected);
                }
                int new_sc = calc_prefix_score(candidate);
                int delta = new_sc - current_sc;
                if (delta >= 0) {
                    current_sc = new_sc;
                    if (current_sc > best_sc) {
                        cerr << "best: loop=" << loop << " current_sc=" << current_sc << "\n";
                        best_sc = current_sc;
                        best_ans = current_ans;
                    }
                    improved = true;
                    break;  // 改善があれば内側ループを終了して外側に戻る
                } else {
                    // 改善が見込めなかった場合、変更をロールバック
                    current_ans[k] = old_val;
                    for (size_t j = 0; j < affected.size(); j++) {
                        satisfied[affected[j]] = old_sat[j];
                    }
                }
            }
            if (!improved) {
                cerr << "not improved\n";
                break;
            }
        }
        return make_pair(best_ans, best_sc);
    }
};

//
// エントリーポイント
//
int main(int argc, char* argv[]) {
    bool DEBUG = false;
    // コマンドライン引数 "--debug" のチェック
    for (int i = 1; i < argc; i++) {
        string arg = argv[i];
        if (arg == "--debug") {
            DEBUG = true;
        }
    }
    TimeKeeper tk;
    double LIMIT = DEBUG ? 0.5 : 1.9;
    int N = 2048;
    int K = 256;
    vector<Condition> X;
    X.reserve(N);
    // 2048 行の入力を受け取る：各行は "a b c p q r"
    for (int i = 0; i < N; i++) {
        int a, b, c, p, q, r;
        if (!(cin >> a >> b >> c >> p >> q >> r))
            break;
        X.push_back({a, b, c, p, q, r});
    }
    Solver solver(N, K, X);
    auto result = solver.solve(tk, LIMIT);
    vector<int> best_ans = result.first;
    int sc = solver.calscore(best_ans);
    // 答えは反転（末尾から出力）して1行に連結して出力
    for (int i = K - 1; i >= 0; i--) {
        cout << best_ans[i];
    }
    cout << "\n";
    cerr << "SC " << sc << "\n";
    return 0;
}