#1138344 (C++17) No.3410 Happiest Art

• 問題: No.3410 Happiest Art
• ユーザー: kazuppa
• 提出日時: 2025-12-03 16:26:05
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,605 bytes
• コンパイル時間: 2,282 ms
• コンパイル使用メモリ: 208,744 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2025-12-16 23:31:52
• 合計ジャッジ時間: 6,809 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

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

ソースコード

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, U;
    if(!(cin >> N >> U)) return 0;
    int H, W;
    cin >> H >> W;
    int HW = H * W;

    vector<int> F(N);
    vector<string> S(N, string());
    for(int i=0;i<N;i++){
        cin >> F[i];
        string grid;
        grid.reserve(HW);
        for(int r=0;r<H;r++){
            string row; cin >> row;
            grid += row;
        }
        S[i] = grid;
    }

    // weights: 1-based i <= U gives +1, else -1
    vector<int> wt(N);
    for(int i=0;i<N;i++) wt[i] = (i < U ? 1 : -1);

    // helper: compute score from d
    auto score_from_d = [&](const vector<int>& d)->int{
        int s=0;
        for(int i=0;i<N;i++) if(d[i] <= F[i]) s += wt[i];
        return s;
    };

    // initial g: majority vote
    string g(HW, '.');
    for(int p=0;p<HW;p++){
        int cnt = 0;
        for(int i=0;i<N;i++) if(S[i][p] == '#') cnt++;
        g[p] = (cnt * 2 >= N ? '#' : '.');
    }

    // compute initial d
    vector<int> d(N,0);
    for(int i=0;i<N;i++){
        int cnt=0;
        for(int p=0;p<HW;p++) if(S[i][p] != g[p]) cnt++;
        d[i] = cnt;
    }
    int cur_score = score_from_d(d);

    // best
    string best_g = g;
    vector<int> best_d = d;
    int best_score = cur_score;

    // RNG
    std::mt19937_64 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    uniform_real_distribution<double> unif01(0.0, 1.0);
    uniform_int_distribution<int> pos_dist(0, HW-1);

    // parameters (tweakable)
    const double TIME_LIMIT = 1.8; // seconds (adjust if needed)
    const double T0 = 1.0;   // initial temperature
    const double TEND = 1e-4; // final temperature
    const int RESTARTS = 6;  // number of restarts (including majority-start)
    const int MAX_NO_IMPROVE_ITER = 2000;

    auto now = chrono::high_resolution_clock::now;
    auto start_time = now();

    // perform multiple runs (first run is majority initial, others random perturbations)
    for(int run = 0; run < RESTARTS; ++run){
        // if time is nearly over, break
        double elapsed = chrono::duration<double>(now() - start_time).count();
        if(elapsed > TIME_LIMIT) break;

        // for runs > 0, create a perturbed initial state (random flips)
        if(run > 0){
            // start from majority then flip some random positions
            g = best_g;
            int flips = max(1, HW/10);
            for(int t=0;t<flips;t++){
                int p = pos_dist(rng);
                g[p] = (g[p] == '#' ? '.' : '#');
            }
            // recompute d and cur_score
            for(int i=0;i<N;i++){
                int cnt = 0;
                for(int p=0;p<HW;p++) if(S[i][p] != g[p]) cnt++;
                d[i] = cnt;
            }
            cur_score = score_from_d(d);
        }

        // simulated annealing main loop
        double T = T0;
        // plan iterations: we will reduce temperature based on time left
        int no_improve = 0;
        int iterations = 0;
        while(true){
            ++iterations;
            // time check
            double t_elapsed = chrono::duration<double>(now() - start_time).count();
            if(t_elapsed > TIME_LIMIT) break;

            // linear/exponential schedule based on elapsed fraction
            double frac = t_elapsed / TIME_LIMIT;
            if(frac > 1.0) frac = 1.0;
            // exponential cooling
            T = T0 * pow(TEND / T0, frac);

            // pick random position to flip
            int p = pos_dist(rng);

            // compute delta score if we flip p
            int delta = 0;
            for(int i=0;i<N;i++){
                bool equal_before = (S[i][p] == g[p]);
                int old_d = d[i];
                int new_d = old_d + (equal_before ? +1 : -1); // equal -> flipping makes unequal (+1), otherwise -1
                bool old_ok = (old_d <= F[i]);
                bool new_ok = (new_d <= F[i]);
                if(old_ok != new_ok){
                    if(new_ok) delta += wt[i];
                    else delta -= wt[i];
                }
            }

            bool accept = false;
            if(delta > 0) accept = true;
            else {
                double prob = exp((double)delta / max(1e-12, T)); // delta<=0 so prob<=1
                double r = unif01(rng);
                if(r < prob) accept = true;
            }

            if(accept){
                // apply flip
                for(int i=0;i<N;i++){
                    bool equal_before = (S[i][p] == g[p]);
                    if(equal_before) d[i]++; else d[i]--;
                }
                g[p] = (g[p] == '#' ? '.' : '#');
                cur_score += delta;

                if(cur_score > best_score){
                    best_score = cur_score;
                    best_g = g;
                    best_d = d;
                    no_improve = 0;
                } else {
                    no_improve++;
                }
            } else {
                no_improve++;
            }

            // exit if too long without improvement
            if(no_improve > MAX_NO_IMPROVE_ITER) break;
        } // end while SA loop

        // time check
        double elapsed_after_run = chrono::duration<double>(now() - start_time).count();
        if(elapsed_after_run > TIME_LIMIT) break;
    } // end runs

    // final output
    cout << best_score << "\n";
    for(int r=0;r<H;r++){
        for(int c=0;c<W;c++) cout << best_g[r*W + c];
        cout << "\n";
    }
    return 0;
}