https://community.topcoder.com/stat?c=round_overview&rd=16079
Easy
累積和で前処理しておけばいいだけです。
struct ChocolateDividingEasy { vector<string> chocolate; int S[2510][2510]; int findBest(vector<string> _chocolate) { chocolate = _chocolate; int n = sz(chocolate), m = sz(chocolate[0]); rep(i, 0, n) { rep(j, 0, m) { S[i + 1][j + 1] = S[i + 1][j] + S[i][j + 1] - S[i][j] + chocolate[i][j] - '0'; } } int res = 0; for(int i = 1; i < n; i++) { for(int j = i + 1; j < n; j++) { for(int k = 1; k < m; k++) { for(int l = k + 1; l < m; l++) { vector<pi> x(3), y(3); x[0] = pi(0, i); y[0] = pi(0, k); x[1] = pi(i, j); y[1] = pi(k, l); x[2] = pi(j, n); y[2] = pi(l, m); vector<int> vec; rep(p, 0, 3) { rep(q, 0, 3) { int x1 = x[p].fst, x2 = x[p].sec; int y1 = y[q].fst, y2 = y[q].sec; vec.pb(S[x2][y2] - S[x2][y1] - S[x1][y2] + S[x1][y1]); } } sort(all(vec)); MAX(res, vec[0]); } } } } return res; } };
Medium
期待値について理解が深まりました。
よく観察すると、二重辺の数=連結成分の数になることがわかります。なぜなら構築したグラフはさきにループを含むDAGになり、またループは3点以上で構成できないからです。
よって期待値の加法定理より、求める値は、
Σ(e∈E)f(e)となります。ここでEは二点のすべてのとり方の集合、fはその二点が二重辺になる確率です。
各eにつきO(N^2)でfが求められるので、全体でO(N^6)となり、N<=20なので間に合います。でもTopCoderは最適化オプションつけないでコンパイルしているみたいで実行時間結構遅かった。
struct ClosestRabbit { vector<string> board; int r; double getExpected(vector<string> _board, int _r) { board = _board, r = _r; int n = sz(board), m = sz(board[0]); int cnt = 0; rep(i, 0, n) rep(j, 0, m) if(board[i][j] == '.') cnt++; double ans = 0.0; rep(i, 0, n) { rep(j, 0, m) { rep(k, 0, n) { rep(l, 0, m) { if(board[i][j] == '#' || board[k][l] == '#') continue; if(i == k && j == l) continue; double tmp = 1.0 * r * (r - 1) / (cnt * (cnt - 1)); double dist = sqrt(1.0 * (i - k) * (i - k) + (j - l) * (j - l)); int cnta = 0; rep(x, 0, n) { rep(y, 0, m) { if(board[x][y] == '#') continue; double d1 = sqrt(1.0 * (i - x) * (i - x) + (j - y) * (j - y)); double d2 = sqrt(1.0 * (k - x) * (k - x) + (l - y) * (l - y)); if(dist > d1 + eps) continue; if(dist > d2 + eps) continue; if(d1 - eps < dist && dist < d1 + eps) { if(x < k) continue; else if(x == k) { if(y < l) continue; } } if(d2 - eps < dist && dist < d2 + eps) { if(x < i) continue; else if(x == i) { if(y < j) continue; } } cnta++; } } if(cnta < r - 2) continue; rep(t, 0, r - 2) { tmp = tmp * 1.0 * (cnta - t) / (cnt - 2 - t); } ans += tmp; } } } } return ans / 2; } };
