#include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; using pi=pair; // using mint=modint998244353; using mint=modint1000000007; // using mint2=static_modint<2>; // using BoostPoint=boost::polygon::point_data; // using Voronoi=boost::polygon::voronoi_diagram; // using mint=LazyMontgomeryModInt<998244353>; using vm=vector; // using vvm=vector; #line 2 "hashmap/hashmap.hpp" #line 2 "hashmap/hashmap-base.hpp" #include using namespace std; namespace HashMapImpl { using u32 = uint32_t; using u64 = uint64_t; template struct HashMapBase; template struct itrB : iterator { using base = iterator; using ptr = typename base::pointer; using ref = typename base::reference; u32 i; HashMapBase* p; explicit constexpr itrB() : i(0), p(nullptr) {} explicit constexpr itrB(u32 _i, HashMapBase* _p) : i(_i), p(_p) {} explicit constexpr itrB(u32 _i, const HashMapBase* _p) : i(_i), p(const_cast*>(_p)) {} friend void swap(itrB& l, itrB& r) { swap(l.i, r.i), swap(l.p, r.p); } friend bool operator==(const itrB& l, const itrB& r) { return l.i == r.i; } friend bool operator!=(const itrB& l, const itrB& r) { return l.i != r.i; } const ref operator*() const { return const_cast*>(p)->data[i]; } ref operator*() { return p->data[i]; } ptr operator->() const { return &(p->data[i]); } itrB& operator++() { assert(i != p->cap && "itr::operator++()"); do { i++; if (i == p->cap) break; if (p->occupied_flag[i] && !p->deleted_flag[i]) break; } while (true); return (*this); } itrB operator++(int) { itrB it(*this); ++(*this); return it; } itrB& operator--() { do { i--; if (p->occupied_flag[i] && !p->deleted_flag[i]) break; assert(i != 0 && "itr::operator--()"); } while (true); return (*this); } itrB operator--(int) { itrB it(*this); --(*this); return it; } }; template struct HashMapBase { using u32 = uint32_t; using u64 = uint64_t; using iterator = itrB; using itr = iterator; protected: template inline u64 randomized(const K& key) const { return u64(key) ^ r; } template ::value, nullptr_t> = nullptr, enable_if_t::value, nullptr_t> = nullptr> inline u32 inner_hash(const K& key) const { return (randomized(key) * 11995408973635179863ULL) >> shift; } template < typename K, enable_if_t::value, nullptr_t> = nullptr, enable_if_t::value, nullptr_t> = nullptr, enable_if_t::value, nullptr_t> = nullptr> inline u32 inner_hash(const K& key) const { u64 a = randomized(key.first), b = randomized(key.second); a *= 11995408973635179863ULL; b *= 10150724397891781847ULL; return (a + b) >> shift; } template ::value, nullptr_t> = nullptr, enable_if_t::value, nullptr_t> = nullptr> inline u32 inner_hash(const K& key) const { static constexpr u64 mod = (1LL << 61) - 1; static constexpr u64 base = 950699498548472943ULL; u64 res = 0; for (auto& elem : key) { __uint128_t x = __uint128_t(res) * base + (randomized(elem) & mod); res = (x & mod) + (x >> 61); } __uint128_t x = __uint128_t(res) * base; res = (x & mod) + (x >> 61); if (res >= mod) res -= mod; return res >> (shift - 3); } template ::value, nullptr_t> = nullptr> inline u32 hash(const D& dat) const { return inner_hash(dat); } template < typename D = Data, enable_if_t::value, nullptr_t> = nullptr> inline u32 hash(const D& dat) const { return inner_hash(dat.first); } template ::value, nullptr_t> = nullptr> inline Key data_to_key(const D& dat) const { return dat; } template < typename D = Data, enable_if_t::value, nullptr_t> = nullptr> inline Key data_to_key(const D& dat) const { return dat.first; } void reallocate(u32 ncap) { vector ndata(ncap); vector nf(ncap); shift = 64 - __lg(ncap); for (u32 i = 0; i < cap; i++) { if (occupied_flag[i] && !deleted_flag[i]) { u32 h = hash(data[i]); while (nf[h]) h = (h + 1) & (ncap - 1); ndata[h] = move(data[i]); nf[h] = true; } } data.swap(ndata); occupied_flag.swap(nf); cap = ncap; occupied = s; deleted_flag.resize(cap); fill(std::begin(deleted_flag), std::end(deleted_flag), false); } inline bool extend_rate(u32 x) const { return x * 2 >= cap; } inline bool shrink_rate(u32 x) const { return HASHMAP_DEFAULT_SIZE < cap && x * 10 <= cap; } inline void extend() { reallocate(cap << 1); } inline void shrink() { reallocate(cap >> 1); } public: u32 cap, s, occupied; vector data; vector occupied_flag, deleted_flag; u32 shift; static u64 r; static constexpr uint32_t HASHMAP_DEFAULT_SIZE = 4; explicit HashMapBase() : cap(HASHMAP_DEFAULT_SIZE), s(0), occupied(0), data(cap), occupied_flag(cap), deleted_flag(cap), shift(64 - __lg(cap)) {} itr begin() const { u32 h = 0; while (h != cap) { if (occupied_flag[h] && !deleted_flag[h]) break; h++; } return itr(h, this); } itr end() const { return itr(this->cap, this); } friend itr begin(const HashMapBase& h) { return h.begin(); } friend itr end(const HashMapBase& h) { return h.end(); } itr find(const Key& key) const { u32 h = inner_hash(key); while (true) { if (occupied_flag[h] == false) return this->end(); if (data_to_key(data[h]) == key) { if (deleted_flag[h] == true) return this->end(); return itr(h, this); } h = (h + 1) & (cap - 1); } } bool contain(const Key& key) const { return find(key) != this->end(); } itr insert(const Data& d) { u32 h = hash(d); while (true) { if (occupied_flag[h] == false) { if (extend_rate(occupied + 1)) { extend(); h = hash(d); continue; } data[h] = d; occupied_flag[h] = true; ++occupied, ++s; return itr(h, this); } if (data_to_key(data[h]) == data_to_key(d)) { if (deleted_flag[h] == true) { data[h] = d; deleted_flag[h] = false; ++s; } return itr(h, this); } h = (h + 1) & (cap - 1); } } // tips for speed up : // if return value is unnecessary, make argument_2 false. itr erase(itr it, bool get_next = true) { if (it == this->end()) return this->end(); s--; if (!get_next) { this->deleted_flag[it.i] = true; if (shrink_rate(s)) shrink(); return this->end(); } itr nxt = it; nxt++; this->deleted_flag[it.i] = true; if (shrink_rate(s)) { Data d = data[nxt.i]; shrink(); it = find(data_to_key(d)); } return nxt; } itr erase(const Key& key) { return erase(find(key)); } int count(const Key& key) { return find(key) == end() ? 0 : 1; } bool empty() const { return s == 0; } int size() const { return s; } void clear() { fill(std::begin(occupied_flag), std::end(occupied_flag), false); fill(std::begin(deleted_flag), std::end(deleted_flag), false); s = occupied = 0; } void reserve(int n) { if (n <= 0) return; n = 1 << min(23, __lg(n) + 2); if (cap < u32(n)) reallocate(n); } }; template uint64_t HashMapBase::r = chrono::duration_cast( chrono::high_resolution_clock::now().time_since_epoch()) .count(); } // namespace HashMapImpl /** * @brief Hash Map(base) (ハッシュマップ・基底クラス) */ #line 4 "hashmap/hashmap.hpp" template struct HashMap : HashMapImpl::HashMapBase> { using base = typename HashMapImpl::HashMapBase>; using HashMapImpl::HashMapBase>::HashMapBase; using Data = pair; Val& operator[](const Key& k) { typename base::u32 h = base::inner_hash(k); while (true) { if (base::occupied_flag[h] == false) { if (base::extend_rate(base::occupied + 1)) { base::extend(); h = base::hash(k); continue; } base::data[h].first = k; base::data[h].second = Val(); base::occupied_flag[h] = true; ++base::occupied, ++base::s; return base::data[h].second; } if (base::data[h].first == k) { if (base::deleted_flag[h] == true) { base::data[h].second = Val(); base::deleted_flag[h] = false; ++base::s; } return base::data[h].second; } h = (h + 1) & (base::cap - 1); } } typename base::itr emplace(const Key& key, const Val& val) { return base::insert(Data(key, val)); } }; /* * @brief ハッシュマップ(連想配列) * @docs docs/hashmap/hashmap.md **/ struct node{ int score=0,i=-1,k=-1; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /** * O(NM) ,M=H*W * * M<=10 の場合: * 考えられるグリッドは高々 2^10 個なので全探索する * ここはO(2^10*NM) * * M>=11、正の幸福度の場合: * ハミング距離を2つのグリッド間で異なるマスの数とし * S[i] から距離 F[i] 以下のグリッドの集合をハミング球と考える * * 幸福度が正なら、少なくとも1人の好きな人を満足させる必要があるため、 * 好きな人のハミング球の和集合だけを候補にすれば良い * * まず好きな人のハミング球を列挙し、候補をハッシュ表に登録する * 次に全員のハミング球を列挙し、表に存在する候補に重みを加算する * このように両側から列挙してハッシュで照合することで、 * 球同士を比較せずに、共通するグリッドを直接見つけられる * * 各球は高々 M+1 個のグリッドしか含まず、 * Zobrist hash により1マス反転後のハッシュも O(1) で求まる * ここは O(NM) * * M>=11、幸福度が0の場合: * 全員と2マス以上異なるグリッドが必ず存在し、幸福度0を達成できる * 最初の11マスだけ考えると、各 S[i] が禁止するパターンは * 自身とその1ビット反転の12通りだけ * 12N<=1200<2048=2^11 ので、禁止されないパターンが必ず存在する * 禁止パターンをすべて記録し、残ったものを先頭11マスに採用する * それ以降のマスは任意で良い * ここはO(2^11+N+M) */ int N,U,H,W; cin>>N>>U>>H>>W; int M=H*W; vi F(N),w(N); vectorS(N); rep(i,0,N){ cin>>F[i]; rep(j,0,H){ string row; cin>>row; S[i]+=row; } w[i]=(i>k)&1)?'#':'.'; if(c!=S[i][k])d++; if(d>F[i])break; } if(d<=F[i])score+=w[i]; } if(score>mx){ mx=score; argmx=mask; } } cout<>k)&1)?'#':'.'); } cout<<'\n'; } return 0; } // M>=11、正の幸福度の場合: mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ull unsigned long long vectorz(M),h(N); rep(i,0,M)z[i]=rng(); rep(i,0,N)rep(j,0,M)if(S[i][j]=='#')h[i]^=z[j]; HashMapmp; int lim=U; rep(i,0,U)lim+=F[i]*M; mp.reserve(lim); rep(i,0,U){ mp.emplace(h[i],{0,i,-1}); if(F[i]){ rep(k,0,M)mp.emplace(h[i]^z[k],{0,i,k}); } } rep(i,0,N){ auto it=mp.find(h[i]); if(it!=mp.end())it->second.score+=w[i]; if(F[i]){ rep(k,0,M){ it=mp.find(h[i]^z[k]); if(it!=mp.end())it->second.score+=w[i]; } } } int mx=INT_MIN; pi argmx; for(auto& [key,v]:mp){ if(v.score>mx){ mx=v.score; argmx={v.i,v.k}; } } if(mx>=0){ cout<=11、幸福度が0の場合: vector bad(1<<11); rep(i,0,N){ int mask=0; rep(k,0,11)if(S[i][k]=='#')mask|=(1<>k)&1)ans[k]='#'; rep(j,0,H)cout<