SRM 638

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。