結果

問題 No.3410 Happiest Art
コンテスト
ユーザー GOTKAKO
提出日時 2025-12-17 00:43:49
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,837 ms / 4,000 ms
コード長 2,976 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,216 ms
コンパイル使用メモリ 206,524 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-17 00:44:01
合計ジャッジ時間 11,179 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

random_device rnd;
mt19937 mt(rnd());

char S[100][100][100];
string G[100],best[100];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,U; cin >> N >> U;
    int H,W; cin >> H >> W;
    vector<int> F(N);
    for(int i=0; i<N; i++){
        int f; cin >> f; F.at(i) = f;
        for(int k=0; k<H; k++) for(int l=0; l<W; l++) cin >> S[i][k][l];
    }
    for(int i=0; i<H; i++) G[i].resize(W);


    int answer = -1001001001,now = 0;
    for(int i=0; i<H; i++) for(int k=0; k<W; k++) G[i][k] = S[0][i][k];

    if(H*W <= 18){
        auto dfs = [&](auto dfs,int x,int y) -> void {
            if(y == W) y = 0,x++;
            if(x == H){
                now = 0;
                for(int i=0; i<N; i++){
                    int ng = 0;
                    for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S[i][k][l] != G[k][l]) ng++;
                    if(ng <= F.at(i)) now += (i<U?1:-1);
                }
                if(answer < now) for(int i=0; i<H; i++) best[i] = G[i];
                answer = max(answer,now);

                return;
            }
            G[x][y] = '.';
            dfs(dfs,x,y+1);
            G[x][y] = '#';
            dfs(dfs,x,y+1);
        };
        dfs(dfs,0,0);
        cout << answer << "\n";
        for(int i=0; i<H; i++) cout << best[i] << "\n";
        return 0;
    }
    answer = 0;
    {
        vector<string> zero(H,string(W,'.'));
        while(true){
            for(auto &h : zero) for(auto &w : h) w = mt()%2?'#':'.';
            bool ok = true;
            for(int i=0; i<N; i++){
                int ng = 0;
                for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S[i][k][l] != zero[k][l]) ng++;
                if(ng <= F.at(i)) ok = false;
            }
            if(ok){
                for(int i=0; i<H; i++) best[i] = zero[i];
                break;
            }
        }
    }
    now = 1;
    vector<int> NG(N);
    for(int i=1; i<N; i++){
        for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S[i][k][l] != G[k][l]) NG.at(i)++;
        if(NG.at(i) <= F.at(i)) now += (i<U?1:-1);
    }
    auto update = [&]() -> void {
        if(answer >= now) return;
        answer = now;
        for(int i=0; i<H; i++) best[i] = G[i];
    };
    auto change = [&](int x,int y) -> void {
        for(int i=0; i<N; i++){
            if(NG.at(i) <= F.at(i)) now -= (i<U?1:-1);
            if(S[i][x][y] != G[x][y]) NG.at(i)--;
            else NG.at(i)++;
            if(NG.at(i) <= F.at(i)) now += (i<U?1:-1);
        }
        G[x][y] ^= '.'^'#';
    };
    for(int i=0; i<U; i++){
        if(i) for(int k=0; k<H; k++) for(int l=0; l<W; l++) if(S[i][k][l] != G[k][l]) change(k,l);
        update();
        for(int k=0; k<H; k++) for(int l=0; l<W; l++){
            change(k,l);
            update();
            change(k,l);
        }    
    }

    cout << answer << "\n";
    for(int i=0; i<H; i++) cout << best[i] << "\n";
}
0