SRM 639

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16082

Easy
なんも難しいことないのに題意勘違いして無限に時間溶かした。さらにオーバーフローもするしいいことなし。

struct AliceGame {
  long long x;
  long long y;
  long long findMinimumValue(long long _x, long long _y) {
    x = _x, y = _y;
	ll s = x + y;
	ll n = 0;
	for(int i = 1; i <= s; i += 2) {
		n++; s -= i;
	}
	if(s != 0) return -1;
	for(ll k = 0; k <= n; k++) {
		if(k * k <= x && x <= (2 * n - k) * k && (x - k) % 2 == 0) return k;
	}
    return -1;
  }
};

Medium
rowとcolumnに分けて考えることができます。
求めるものは(rowのみに並行に折った時の状態数)*(columnのみに並行に折った時の状態数)です。
対称性よりrowのみについて考えます。
紙が[l, r)をカバーする長方形になったとします。
次の状態としてありうるのは[l, i)をrの方向へ折った時と[i, r)をlの方向へ折った時の2通りです。
iをl < i < rを満たすものついてすべて試して、折れるかどうかはO(r - l)で調べられるので、メモ化して数えるとO(N^4)とかになりますが、折れるかどうかは前処理で計算できて、結局O(N^3)になります。

ちゃんと実装分割して考えればそんなバグらせないこともわかった。

struct BoardFolding {
  int N;
  int M;
  bool fold[300][300];
  bool ufold[300][300], lfold[300][300];
  bool dp[300][300];
  int tonumber(char c) {
	  if('0' <= c && c <= '9') return c - '0';
	  else if('a' <= c && c <= 'z') return c - 'a' + 10;
	  else if('A' <= c && c <= 'Z') return c - 'A' + 36;
	  else if(c == '#') return 62;
	  else return 63;
  }

  void loop(int l, int r) {
	  // debug(l, r);
	  if(dp[l][r] == true) return;
	  dp[l][r] = true;
	  for(int i = l + 1; i < r; i++) {
		  if(2 * i - l > r) continue;
		  if(ufold[l][i]) loop(i, r);
	  }
	  for(int i = l + 1; i < r; i++) {
		  if(2 * i - r < l) continue;
		  if(lfold[i][r]) loop(l, i);
	  }
  }
  int solve_sub(const vector<vi>& paper) {
	  int n = sz(paper), m = sz(paper[0]);
	  memset(fold, 0, sizeof(fold));
	  memset(ufold, 0, sizeof(ufold));
	  memset(lfold, 0, sizeof(lfold));
	  memset(dp, 0, sizeof(dp));
	  rep(i, 0, n) {
		  rep(j, 0, n) {
			  bool found = false;
			  rep(k, 0, m) {
				  if(paper[i][k] != paper[j][k]) found = true;
			  }
			  if(!found) fold[i][j] = true;
		  }
	  }
	  rep(i, 0, n) {
		  rep(j, i + 1, n) {
			  if(2 * j - i > n) continue;
			  bool found = false;
			  rep(k, 0, j - i) {
				  if(!fold[j - k - 1][j + k]) found = true;
			  }
			  if(!found) ufold[i][j] = true;
		  }
	  }
	  rep(i, 1, n + 1) {
		  rep(j, i + 1, n + 1) {
			  if(2 * i - j < 0) continue;
			  bool found = false;
			  rep(k, 0, j - i) {
				  if(!fold[i - k - 1][i + k]) found = true;
			  }
			  if(!found) lfold[i][j] = true;
		  }
	  }
	  // rep(i, 0, n + 1) 
		 //  rep(j, 0, n + 1) debug(i, j, fold[i][j], ufold[i][j], lfold[i][j]);
	  loop(0, n);
	  int res = 0;
	  rep(i, 0, n + 1) 
		  rep(j, 0, n + 1) {
			  // debug(i, j, dp[i][j]);
			  res += dp[i][j];
		  }
	  // debug(res);
	  return res;
  }
  vector<string> compressedPaper;
  int howMany(int _N, int _M, vector<string> _compressedPaper) {
    N = _N, M = _M, compressedPaper = _compressedPaper;
	vector<vi> paper(N, vi(M, 0));
	int ans = 1;
	rep(i, 0, N) 
		rep(j, 0, M) 
			paper[i][j] = (tonumber(compressedPaper[i][j / 6]) >> (j % 6)) % 2;
	ans *= solve_sub(paper);
	vector<vi> paper1(M, vi(N, 0));
	rep(i, 0, M) 
		rep(j, 0, N) 
			paper1[i][j] = paper[j][i];
	ans *= solve_sub(paper1);
	return ans;
  }
};