[AtCoder] HHKB プログラミングコンテスト 2020 E – Lamps
問題
方針
照らされるマスについて
散らかっていないマス \( (i, j) \)に照明を置いたとき、水平方向を照らすマスの数を \( a(i, j) \) とし、垂直方向を照らすマスの数を \( b(i, j) \) とします。このとき、照らされるマスの合計は \( a(i, j) + b(i, j) – 1\) となります。これらは、Union-Find を使うことで求めることができます。つまり、マス \( (i, j)\) と連結なマスの個数が \( a(i, j) + b(i, j) – 1\) 個あるということです。
マス \( (i, j) \) は、\( Wi + j \) とすることで、\( 1 \) 次元配列として扱うことができます。
照明の置き方
散らかっていないマスの個数を \( n \) とします。マス \( (i, j) \) が照らされる照明の置き方は、マス \( (i, j)\) と連結なマスに \( 1 \) 個以上照明を置く場合の数とマス \( (i, j)\) と連結でないマスの照明の置き方の積なので、\( t_i = a(i, j) + b(i, j) – 1 \) として、
\[ (2^{t_i} – 1) 2^{n – t_i}\]
となります。したがって、全ての散らかっていないマスに対して、上記を求めて足し上げます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1000000007; struct dsu { public: int group_num; dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1), group_num(n) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; group_num--; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; }; ll modpow(ll a, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int main() { ll H, W; cin >> H >> W; string S[H]; for (int i = 0; i < H; i++) { cin >> S[i]; } dsu dH(H * W), dV(H * W); for (int i = 0; i < H; i++) { for (int j = 0; j < W - 1; j++) { int id = W * i + j; if (S[i][j] == '.' && S[i][j + 1] == '.') { dH.merge(id, id + 1); } } } for (int i = 0; i < W; i++) { for (int j = 0; j < H - 1; j++) { int id = W * j + i; if (S[j][i] == '.' && S[j + 1][i] == '.') { dV.merge(id, id + W); } } } ll n = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '.') n++; } } ll ans = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '#') continue; int id = W * i + j; ll t = dH.size(id) + dV.size(id) - 1; ans = (ans + (modpow(2, t, mod) - 1) * modpow(2, n - t, mod) + mod) % mod; } } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません