結果

問題 No.3410 Happiest Art
コンテスト
ユーザー kazuppa
提出日時 2025-12-03 16:24:27
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,838 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,097 ms
コンパイル使用メモリ 201,496 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-16 23:31:49
合計ジャッジ時間 7,294 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int N, U;
    cin >> N >> U;

    int H, W;
    cin >> H >> W;
    int HW = H * W;

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

    // 重み: i<=U が +1, それ以降が -1
    vector<int> wt(N);
    for (int i = 0; i < N; i++) wt[i] = (i < U ? 1 : -1);

    // --- 初期解: 多数決 (simple majority) ---
    string g(HW, '0');
    for (int p = 0; p < HW; p++) {
        int cnt1 = 0;
        for (int i = 0; i < N; i++)
            if (S[i][p] == '#') cnt1++;
        g[p] = (cnt1 * 2 >= N ? '#' : '.');
    }

    // d_i の初期計算
    vector<int> d(N);
    for (int i = 0; i < N; i++) {
        int dist = 0;
        for (int p = 0; p < HW; p++)
            if (S[i][p] != g[p]) dist++;
        d[i] = dist;
    }

    // 現スコア計算
    auto calc_score = [&](const vector<int>& d)->int {
        int sum = 0;
        for (int i = 0; i < N; i++)
            if (d[i] <= F[i]) sum += wt[i];
        return sum;
    };

    int best_score = calc_score(d);

    // --- ヒルクライミング ---
    bool improved = true;
    int ITER = 300;  // 反復回数（これで十分強い）
    while (ITER--) {
        improved = false;

        for (int p = 0; p < HW; p++) {
            // 反転した場合の差分を計算
            int new_score = best_score;
            for (int i = 0; i < N; i++) {
                bool eq_before = (S[i][p] == g[p]);
                bool eq_after  = !eq_before;
                int old_d = d[i];
                int new_d = old_d + (eq_before ? +1 : -1);

                bool old_ok = (old_d <= F[i]);
                bool new_ok = (new_d <= F[i]);
                if (old_ok != new_ok) {
                    if (new_ok) new_score += wt[i];
                    else        new_score -= wt[i];
                }
            }

            if (new_score > best_score) {
                // 改善なら反転を採用
                best_score = new_score;
                improved = true;
                // d の更新
                for (int i = 0; i < N; i++) {
                    bool eq_before = (S[i][p] == g[p]);
                    if (eq_before) d[i]++;
                    else           d[i]--;
                }
                g[p] = (g[p] == '#' ? '.' : '#');
            }
        }

        if (!improved) break;
    }

    // 出力
    cout << best_score << "\n";
    for (int x = 0; x < H; x++) {
        for (int y = 0; y < W; y++) cout << g[x*W+y];
        cout << "\n";
    }
}
0