https://community.topcoder.com/stat?c=round_overview&er=5&rd=16081
Easy
まずブロックがないとわかっているところを除外します。
あっても良いブロックで連結成分が何個かできたとします。
この連結成分を同時に2個取ることはできません。また各連結成分でブロックを減らす意味はないので、連結成分ごとに条件を満たすか試せばよいです。
連結成分が1つであることが条件だと勘違いしてWA。ブロックがないときの場合分けでWA。300点だけあってコーナーケースを考慮するのも難しい。
struct ShadowSculpture { vector<string> XY; vector<string> YZ; vector<string> ZX; int n; bool block[11][11][11]; bool used[11][11][11]; bool connect[11][11][11]; int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, 1, -1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; void loop(int x, int y, int z) { used[x][y][z] = true; connect[x][y][z] = true; rep(i, 0, 6) { int nx = x + dx[i], ny = y + dy[i], nz = z + dz[i]; if(nx < 0 || n <= nx || ny < 0 || n <= ny || nz < 0 || n <= nz) continue; if(!used[nx][ny][nz] && block[nx][ny][nz]) loop(nx, ny, nz); } } bool checker() { vector<string> txy = XY; vector<string> tyz = YZ; vector<string> tzx = ZX; rep(i, 0, n) { rep(j, 0, n) { rep(k, 0, n) { if(connect[i][j][k]) { txy[i][j] = 'N'; tyz[j][k] = 'N'; tzx[k][i] = 'N'; } } } } rep(i, 0, n) rep(j, 0, n) { if(txy[i][j] == 'Y' || tyz[i][j] == 'Y' || tzx[i][j] == 'Y') return false; } return true; } string possible(vector<string> _XY, vector<string> _YZ, vector<string> _ZX) { XY = _XY, YZ = _YZ, ZX = _ZX; n = sz(XY); rep(i, 0, n) { rep(j, 0, n) { rep(k, 0, n) block[i][j][k] = true; } } rep(i, 0, n) { rep(j, 0, n) { if(XY[i][j] == 'N') { rep(k, 0, n) { block[i][j][k] = false; } } } } rep(i, 0, n) { rep(j, 0, n) { if(YZ[i][j] == 'N') { rep(k, 0, n) { block[k][i][j] = false; } } } } rep(i, 0, n) { rep(j, 0, n) { if(ZX[i][j] == 'N') { rep(k, 0, n) { block[j][k][i] = false; } } } } bool found = false; bool found2 = false; rep(i, 0, n) { rep(j, 0, n) { if(XY[i][j] == 'Y' || YZ[i][j] == 'Y' || ZX[i][j] == 'Y') found2 = true; rep(k, 0, n) { if(block[i][j][k]) found = true; } } } if(!found) { if(!found2) return "Possible"; else return "Impossible"; } rep(i, 0, n) { rep(j, 0, n) { rep(k, 0, n) { if(block[i][j][k] && !used[i][j][k]) { memset(connect, 0, sizeof(connect)); loop(i, j, k); if(checker()) return "Possible"; } } } } return "Impossible"; } };
49 minutes 49 secs、2WAしたとしても遅すぎる。printデバッグする回数が減ればいいんだけど…
Medium
良問だと思う。
まず一番大きい要素をvとして、vよりも右側にあって、かつvとの和がmaxSizeSumを超えるものはvより左側にはいけません。
同じようにvより左側の要素についても言えます。しかしvとの和がmaxSizeSumより小さい要素は、permutationのどの順番にも来ていいので、配列を一番大きい要素で二分して再起的に解けばよいです。
struct NarrowPassage2 { vector<int> size; int maxSizeSum; ll loop(vector<int> vec) { if(sz(vec) <= 1) return 1; int n = sz(vec); int at = -1, mv = -1; rep(i, 0, n) { if(vec[i] > mv) { mv = vec[i]; at = i; } } vector<int> lvec, rvec; int cnt = 0; rep(i, 0, at) { if(vec[i] + vec[at] > maxSizeSum) { lvec.pb(vec[i]); } else cnt++; } rep(i, at + 1, n) { if(vec[i] + vec[at] > maxSizeSum) { rvec.pb(vec[i]); } else cnt++; } ll ans = 1; MUL(ans, loop(lvec)); MUL(ans, loop(rvec)); rep(i, 0, cnt) { MUL(ans, n - i); } return ans; } int count(vector<int> _size, int _maxSizeSum) { size = _size, maxSizeSum = _maxSizeSum; return loop(size); } };
トポロジカルソートのなんかだと思ったけど全然違って面白かった。
トポロジカルソートを数えるのはやっぱりO(N*2^N)かかりそう。
考察は永遠と時間を使ったけど、実装だけなら4 minutes 44 secs。