#1172443 (C++23(gcc16)) No.3730 Jagged Minesweeper

• 問題: No.3730 Jagged Minesweeper
• ユーザー: 👑 kencho
• 提出日時: 2026-07-22 04:16:39
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 7,647 bytes
• コンパイル時間: 3,273 ms
• コンパイル使用メモリ: 367,152 KB
• 実行使用メモリ: 15,704 KB
• 最終ジャッジ日時: 2026-09-19 12:36:58
• 合計ジャッジ時間: 74,498 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 13 WA * 30

ソースコード

#include <bits/stdc++.h>
using namespace std;

#ifndef TIME_LIMIT
#define TIME_LIMIT 1.9
#endif

struct RNG {
    uint64_t s;
    RNG() : s(chrono::high_resolution_clock::now().time_since_epoch().count()) {}
    uint64_t next() { s ^= s << 7; s ^= s >> 9; return s; }
    int operator()(int n) { return int(next() % (uint64_t)n); }
    double real() { return (next() >> 11) * (1.0 / 9007199254740992.0); }
};

struct Solver {
    int N, V;
    vector<unsigned char> a, x, cnt;
    vector<int> bad, pos;
    vector<unsigned char> best_x;
    long long score = 0, best_score = (1LL << 60);
    RNG rng;
    chrono::steady_clock::time_point start_time;

    Solver(int n, vector<unsigned char> aa)
        : N(n), V(n * n), a(move(aa)), x(V), cnt(V), pos(V, -1) {}

    double elapsed() const {
        return chrono::duration<double>(chrono::steady_clock::now() - start_time).count();
    }

    // Contestant-style objective: violated-cell count + a small penalty for depth.
    // This is not the intended cut/potential function.
    int cost(int id) const {
        int gap;
        if (x[id]) gap = max(0, (int)cnt[id] - (int)a[id] + 1); // need cnt < a
        else       gap = max(0, (int)a[id] - (int)cnt[id]);     // need cnt >= a
        return gap ? 16 + gap : 0;
    }

    void change_bad(int id, bool now_bad) {
        if (now_bad) {
            if (pos[id] == -1) {
                pos[id] = (int)bad.size();
                bad.push_back(id);
            }
        } else if (pos[id] != -1) {
            int p = pos[id], last = bad.back();
            bad[p] = last;
            pos[last] = p;
            bad.pop_back();
            pos[id] = -1;
        }
    }

    void init(int type) {
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int id = r * N + c;
                if (type == 0) x[id] = 0;                       // all empty
                else if (type == 1) x[id] = rng(2);             // random
                else if (type == 2) x[id] = (r + c) & 1;        // checkerboard
                else x[id] = c & 1;                             // vertical stripes
            }
        }

        fill(cnt.begin(), cnt.end(), 0);
        for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c) {
            int id = r * N + c;
            if (!x[id]) continue;
            for (int dr = -1; dr <= 1; ++dr) for (int dc = -1; dc <= 1; ++dc) {
                if (dr == 0 && dc == 0) continue;
                int nr = r + dr, nc = c + dc;
                if (0 <= nr && nr < N && 0 <= nc && nc < N) ++cnt[nr * N + nc];
            }
        }

        bad.clear();
        fill(pos.begin(), pos.end(), -1);
        score = 0;
        for (int id = 0; id < V; ++id) {
            int z = cost(id);
            score += z;
            if (z) change_bad(id, true);
        }
        save_best();
    }

    void save_best() {
        if (score < best_score) {
            best_score = score;
            best_x = x;
        }
    }

    int affected_cells(const int *mv, int k, int *out) const {
        int m = 0;
        for (int z = 0; z < k; ++z) {
            int r = mv[z] / N, c = mv[z] % N;
            for (int dr = -1; dr <= 1; ++dr) for (int dc = -1; dc <= 1; ++dc) {
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                int id = nr * N + nc;
                bool seen = false;
                for (int i = 0; i < m; ++i) if (out[i] == id) { seen = true; break; }
                if (!seen) out[m++] = id;
            }
        }
        return m;
    }

    void toggle(const int *mv, int k) {
        for (int z = 0; z < k; ++z) {
            int id = mv[z], r = id / N, c = id % N;
            int d = x[id] ? -1 : 1;
            x[id] ^= 1;
            for (int dr = -1; dr <= 1; ++dr) for (int dc = -1; dc <= 1; ++dc) {
                if (dr == 0 && dc == 0) continue;
                int nr = r + dr, nc = c + dc;
                if (0 <= nr && nr < N && 0 <= nc && nc < N)
                    cnt[nr * N + nc] = (unsigned char)((int)cnt[nr * N + nc] + d);
            }
        }
    }

    int delta_of(const int *mv, int k) {
        int af[36], m = affected_cells(mv, k, af);
        int old_sum = 0, new_sum = 0;
        for (int i = 0; i < m; ++i) old_sum += cost(af[i]);
        toggle(mv, k);
        for (int i = 0; i < m; ++i) new_sum += cost(af[i]);
        toggle(mv, k);
        return new_sum - old_sum;
    }

    void apply(const int *mv, int k, int delta) {
        int af[36], m = affected_cells(mv, k, af);
        toggle(mv, k);
        score += delta;
        for (int i = 0; i < m; ++i) change_bad(af[i], cost(af[i]) != 0);
        save_best();
    }

    int random_bad_or_global(bool mainly_bad = true) {
        if (mainly_bad && !bad.empty() && rng(100) < 90) return bad[rng((int)bad.size())];
        return rng(V);
    }

    void make_move(bool pair_move, int *mv, int &k) {
        int anchor = random_bad_or_global();
        if (!pair_move || N == 1) {
            mv[0] = anchor;
            k = 1;
            return;
        }
        int r = anchor / N, c = anchor % N;
        static const int dr[8] = {-1,-1,-1,0,0,1,1,1};
        static const int dc[8] = {-1,0,1,-1,1,-1,0,1};
        int z = rng(8), nr = r + dr[z], nc = c + dc[z];
        if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
            mv[0] = anchor; k = 1;
        } else {
            mv[0] = anchor; mv[1] = nr * N + nc; k = 2;
        }
    }

    bool solve() {
        start_time = chrono::steady_clock::now();
        best_score = (1LL << 60);

        const int STARTS = 4;
        for (int st = 0; st < STARTS; ++st) {
            if (elapsed() >= TIME_LIMIT) break;
            init(st);
            if (score == 0) return true;

            double begin = TIME_LIMIT * st / STARTS;
            double end   = TIME_LIMIT * (st + 1) / STARTS;

            while (elapsed() < end) {
                double p = (elapsed() - begin) / max(1e-9, end - begin);
                p = min(1.0, max(0.0, p));
                double temp = 12.0 * pow(0.03 / 12.0, p);

                bool pair_move = (N >= 2 && rng(100) < 15);
                int trials = pair_move ? 4 : 8;

                int best_mv[4], best_k = 0, best_delta = INT_MAX;
                for (int t = 0; t < trials; ++t) {
                    int mv[4], k;
                    make_move(pair_move, mv, k);
                    int d = delta_of(mv, k);
                    if (d < best_delta) {
                        best_delta = d;
                        best_k = k;
                        for (int i = 0; i < k; ++i) best_mv[i] = mv[i];
                    }
                }

                if (best_delta <= 0 || rng.real() < exp(-(double)best_delta / temp)) {
                    apply(best_mv, best_k, best_delta);
                    if (score == 0) return true;
                }
            }
        }

        x = best_x;
        return best_score == 0;
    }

    void output() const {
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) cout << (x[r * N + c] ? 'o' : '.');
            cout << '\n';
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<unsigned char> a(N * N);
    for (int r = 0; r < N; ++r) {
        string s;
        cin >> s;
        for (int c = 0; c < N; ++c) a[r * N + c] = (unsigned char)(s[c] - '0');
    }

    Solver solver(N, move(a));
    bool ok = solver.solve();
    cerr << "best_score=" << solver.best_score << " solved=" << ok << '\n';
    solver.output();
}