結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<ll(n);i++)






ll N,U,H,W;
ll F[110];
ll f(string x,string y,ll i){

	ll d=0;
	REP(k,H*W) if(x[k]!=y[k]) d++;
	if(d<=F[i]) return 1;
	else return 0;

}









int main(){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j,k;





	cin >> N >> U >> H >> W;

	vector<string> s(N+1);

	for(i=1;i<=N;i++){

		cin >> F[i];

		string x;
		REP(j,H){
			REP(k,W){
				char c;
				cin >> c;
				x+=c;
			}
		}

		s[i]=x;

	}




	vector<string> t;
	for(i=1;i<=U;i++){
		for(j=i;j<=U;j++){

			vector<ll> b;
			REP(k,H*W) if(s[i][k]!=s[j][k]) b.push_back(k);

			if((ll)b.size()==0) t.push_back(s[i]);
			else if((ll)b.size()==1){
				t.push_back(s[i]);
				t.push_back(s[j]);
			}
			else if((ll)b.size()==2){
				string x=s[i];

				x[b[0]]='.';
				x[b[1]]='.';
				t.push_back(x);
				x[b[0]]='#';
				x[b[1]]='#';
				t.push_back(x);

			}

		}
	}


	ll n=t.size();


	if(n==0){

		if(H*W<=6){

			ll mx=-1000;
			string z;
			for(i=0;i<(1LL<<H*W);i++){
				string x;
				for(j=0;j<H*W;j++){
					if(i&(1LL<<j)) x+='.';
					else x+='#';
				}

				ll u=0;
				for(j=1;j<=U;j++){
					u+=f(x,s[j],j);
				}

				ll v=0;
				for(j=U+1;j<=N;j++){
					v+=f(x,s[j],j);
				}


				if(u-v>mx){
					mx=u-v;
					z=x;
				}
			}


			cout << mx << endl;

			REP(i,H*W){
				cout << z[i];
				if((i+1)%W==0) cout << endl;
			}

			return 0;

		}


		if(H*W>=7){

			string z;
			ll mx=-1000;
			for(i=0;i<(1LL<<7);i++){
				string x;
				for(j=0;j<7;j++){
					if(i&(1LL<<j)) x+='.';
					else x+='#';
				}

				REP(j,H*W-7) x+='#';

				ll u=0;
				for(j=1;j<=U;j++){
					u+=f(x,s[j],j);
				}

				ll v=0;
				for(j=U+1;j<=N;j++){
					v+=f(x,s[j],j);
				}


				if(u-v>mx){
					mx=u-v;
					z=x;
				}
			}


			cout << mx << endl;

			REP(i,H*W){
				cout << z[i];
				if((i+1)%W==0) cout << endl;
			}

			return 0;


		}



	}





	sort(t.begin(),t.end());
	t.erase(unique(t.begin(),t.end()),t.end());



	n=t.size();



	ll mx=-1000;
	ll g=-1;
	REP(i,n){

		string x=t[i];

		ll u=0;
		for(j=1;j<=U;j++){
			u+=f(x,s[j],j);
		}

		ll v=0;
		for(j=U+1;j<=N;j++){
			v+=f(x,s[j],j);
		}


		if(u-v>mx){
			mx=u-v;
			g=i;
		}

	}


	if(mx>=0){

		cout << mx << endl;

		REP(i,H*W){
			cout << t[g][i];
			if((i+1)%W==0) cout << endl;
		}

		return 0;
	}







	if(H*W<=6){

		string z;
		for(i=0;i<(1LL<<H*W);i++){
			string x;
			for(j=0;j<H*W;j++){
				if(i&(1LL<<j)) x+='.';
				else x+='#';
			}

			ll u=0;
			for(j=1;j<=U;j++){
				u+=f(x,s[j],j);
			}

			ll v=0;
			for(j=U+1;j<=N;j++){
				v+=f(x,s[j],j);
			}


			if(u-v>mx){
				mx=u-v;
				z=x;
			}
		}


		cout << mx << endl;

		REP(i,H*W){
			cout << z[i];
			if((i+1)%W==0) cout << endl;
		}

		return 0;

	}


	if(H*W>=7){

		string z;
		for(i=0;i<(1LL<<7);i++){
			string x;
			for(j=0;j<7;j++){
				if(i&(1LL<<j)) x+='.';
				else x+='#';
			}

			REP(j,H*W-7) x+='#';

			ll u=0;
			for(j=1;j<=U;j++){
				u+=f(x,s[j],j);
			}

			ll v=0;
			for(j=U+1;j<=N;j++){
				v+=f(x,s[j],j);
			}


			if(u-v>mx){
				mx=u-v;
				z=x;
			}
		}


		cout << mx << endl;

		REP(i,H*W){
			cout << z[i];
			if((i+1)%W==0) cout << endl;
		}

		return 0;





	}








  return 0;

}
0