#1189030 (C++23) No.3730 Jagged Minesweeper

• 問題: No.3730 Jagged Minesweeper
• ユーザー: besukohu
• 提出日時: 2026-09-19 16:23:15
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,020 ms / 2,500 ms
• コード長: 8,145 bytes
• コンパイル時間: 2,765 ms
• コンパイル使用メモリ: 353,952 KB
• 実行使用メモリ: 13,440 KB
• 最終ジャッジ日時: 2026-09-19 16:23:51
• 合計ジャッジ時間: 20,752 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 43

ソースコード

#line 1 "kyopro/main.cpp"
#include <bits/stdc++.h>

#line 3 "kyopro_lib/base.hpp"

#line 5 "kyopro_lib/base.hpp"

using namespace std;
using ll = long long;
using ld = long double;

using i2 = array<ll, 2>;
using i3 = array<ll, 3>;
using i4 = array<ll, 4>;

using f2 = array<ld, 2>;
using f3 = array<ld, 3>;
using f4 = array<ld, 4>;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

template <class T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

const ll INF = (1LL << 61);

bool chmin(auto& a, const auto& b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, const auto& b) { return a < b ? a = b, 1 : 0; }

ll floor_div(ll a, ll b) { return a / b - (a % b != 0 && (a ^ b) < 0); }
ll ceil_div(ll a, ll b) { return a / b + (a % b != 0 && (a ^ b) > 0); }
ll floor_mod(ll a, ll b) { return a % b + (a % b != 0 && (a ^ b) < 0) * b; }

mt19937 mt(time(0));
class xor_shift_128 {
   public:
    typedef uint32_t result_type;
    xor_shift_128(result_type seed = mt()) {
        set_seed(seed);
    }
    void set_seed(result_type seed) {
        a = seed = 1812433253 * (seed ^ (seed >> 30));
        b = seed = 1812433253 * (seed ^ (seed >> 30)) + 1;
        c = seed = 1812433253 * (seed ^ (seed >> 30)) + 2;
        d = seed = 1812433253 * (seed ^ (seed >> 30)) + 3;
    }
    result_type gen() {
        result_type t = (a ^ (a << 11));
        a = b;
        b = c;
        c = d;
        return d = (d ^ (d >> 19)) ^ (t ^ (t >> 8));
    }
    result_type operator()() {
        return gen();
    }
    ll gen_range(ll min_inclusive, ll max_exclusive) {
        ll diff = max_exclusive - min_inclusive;
        assert(diff);
        return min_inclusive + gen() % diff;
    }

    static constexpr result_type max() { return numeric_limits<result_type>::max(); }
    static constexpr result_type min() { return numeric_limits<result_type>::min(); }

   private:
    result_type a, b, c, d;
};
xor_shift_128 xorrand;

template <class T, size_t N>
istream& operator>>(istream& is, array<T, N>& a) {
    for (auto& x : a) is >> x;
    return is;
}
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a) {
    for (size_t i = 0; i < N; i++)
        os << (i ? " " : "") << a[i];
    return os;
}

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++)
        os << (i ? " " : "") << v[i];
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<vector<T>>& vv) {
    for (int i = 0; i < (int)vv.size(); i++)
        os << (i ? "\n" : "") << vv[i];
    return os;
}

#define dbg(...) cerr << #__VA_ARGS__ << " = ", debug_print(__VA_ARGS__);
void debug_print() { cerr << endl; }
template <class T, class... Args>
void debug_print(const T& x, const Args&... args) {
    cerr << x;
    if constexpr (sizeof...(args) > 0) cerr << ", ";
    debug_print(args...);
}

struct sep {
    const char* s;
    sep(const char* s) : s(s) {}
};

template <class... Args>
void print(sep sp, const Args&... args) {
    int i = 0;
    ((cout << (i++ ? sp.s : "") << args), ...);
    cout << "\n";
}

template <class... Args>
void print(const Args&... args) {
    print(sep{" "}, args...);
}

template <class T>
void print(const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++)
        cout << (i ? " " : "") << v[i];
    cout << "\n";
}

template <class T>
void print(sep sp, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++)
        cout << (i ? sp.s : "") << v[i];
    cout << "\n";
}
#line 4 "kyopro/main.cpp"

bool is_multi = false;

ll mod = 998244353;

vector<string> gen(ll n) {
    vector<string> S(n, string(n, '0'));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            S[i][j] = xorrand() % 10 + '0';
        }
    }
    return S;
}

void solve() {
    ll N;
    cin >> N;
    vector<string> S(N);
    cin >> S;

    // N = 1000;
    // S = gen(1000);

    // cout << N << endl;
    // for (auto& s : S) cout << s << endl;

    vector<string> ans(N, string(N, 0));
    vector<vector<ll>> sum(N, vector<ll>(N, 0));

    vector<i2> thth = {
        {0, 0},
        {1, 0},
        {-1, 0},
        {0, -1},
        {1, -1},
        {-1, -1},
        {0, 1},
        {1, 1},
        {-1, 1},
    };

    auto check = [&](ll i, ll j) -> ll {
        return (ans[i][j] ? (max(0LL, sum[i][j] - (ll)(S[i][j] - '0'))) : (max((ll)(S[i][j] - '0') - sum[i][j], 0LL)));
    };

    ll score = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            score += check(i, j);
        }
    }

    auto flip = [&](ll choi, ll choj) -> ll {
        ll diff = 0;
        for (auto [di, dj] : thth) {
            ll i = choi + di;
            ll j = choj + dj;

            if (i < 0 || i >= N || j < 0 || j >= N) continue;

            diff -= check(i, j);
        }

        ll add = (ans[choi][choj] ? -1 : 1);
        ans[choi][choj] ^= 1;
        for (auto [di, dj] : thth) {
            ll i = choi + di;
            ll j = choj + dj;

            if (i < 0 || i >= N || j < 0 || j >= N) continue;
            sum[i][j] += add;
        }

        for (auto [di, dj] : thth) {
            ll i = choi + di;
            ll j = choj + dj;

            if (i < 0 || i >= N || j < 0 || j >= N) continue;

            diff += check(i, j);
        }
        return diff;
    };

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (S[i][j] >= '5') {
                score += flip(i, j);
            }
        }
    }

    auto calc_prob = [](ll diff, double temp) {
        if (diff < 0) {
            return true;
        }
        return exp(-diff / temp) * (1 << 16) > xorrand() % (1 << 16);
    };

    auto modify_flip = [&](double temp) {
        ll choi = xorrand() % N;
        ll choj = xorrand() % N;
        if (check(choi, choj) == 0) {
            return;
        }
        ll diff = flip(choi, choj);

        if (check(choi, choj) == 0) {
            score += diff;
            return;
        }

        flip(choi, choj);
    };

    auto modify_swap = [&](double temp) {
        if (N == 1) return;
        ll choi = xorrand() % (N - 1);
        ll choj = xorrand() % N;
        ll diff = 0;
        for (int i = 0; i < 2; i++) {
            diff += flip(choi + i, choj);
        }

        if (calc_prob(diff, temp)) {
            score += diff;
        } else {
            for (int i = 0; i < 2; i++) {
                diff += flip(choi + i, choj);
            }
        }
    };

    auto modify = [&](double temp) {
        modify_flip(temp);
        // modify_swap(temp);
    };

    auto sa = [&]() {
        auto starttime = chrono::system_clock::now();
        ll timelimit = 1900;
        ll bestscore = score;
        double starttemp = 0, endtemp = 0, nowtemp = starttemp;

        for (ll turn = 0; score; turn++) {
            if ((turn & 31) == 31) {
                ll timediff = duration_cast<chrono::milliseconds>(chrono::system_clock::now() - starttime).count();
                if (timediff > timelimit) {
                    cerr << turn << endl;
                    break;
                }
                nowtemp = endtemp - ((endtemp - starttemp) * pow(timelimit - timediff, 1)) / pow(timelimit, 1);
            }

            if (chmin(bestscore, score)) {
                // cerr << bestscore << endl;
            }

            modify(nowtemp);
        }
    };

    sa();

    cerr << score << endl;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (check(i, j)) {
                dbg(i, j, check(i, j), S[i][j], sum[i][j])
            }
        }
    }

    for (auto& x : ans)
        for (auto& y : x) y = (y ? 'o' : '.');
    print(sep("\n"), ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    ll tests = 1;
    if (is_multi) {
        cin >> tests;
    }

    while (tests--) {
        solve();
    }

    return 0;
}