国内予選出るので精進します。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743&lang=jp
4隅を必ず含む解が存在することが言える。それを元に丁寧に場合分けすればできる。面倒だけど一発AC。
int H, W, N; ll A[210][210]; ll S[210][210]; ll get(int x1, int y1, int x2, int y2) { //[x1 x2)*[y1 y2) return S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]; } bool divide1(int x1, int y1, int x2, int y2, ll m) { //O(1) return get(x1, y1, x2, y2) >= m; } bool divide2(int x1, int y1, int x2, int y2, ll m) { //O(N) bool ok = false; rep(i, x1, x2) { ok |= (divide1(x1, y1, i, y2, m) & divide1(i, y1, x2, y2, m)); } rep(i, y1, y2) { ok |= (divide1(x1, y1, x2, i, m) & divide1(x1, i, x2, y2, m)); } return ok; } bool divide3(int x1, int y1, int x2, int y2, ll m) { //O(N) bool ok = false; rep(i, x1, x2) { if(divide1(x1, y1, i, y2, m)) { ok |= divide2(i, y1, x2, y2, m); break; } } rer(i, x2, x1) { if(divide1(i, y1, x2, y2, m)) { ok |= divide2(x1, y1, i, y2, m); break; } } rep(i, y1, y2) { if(divide1(x1, y1, x2, i, m)) { ok |= divide2(x1, i, x2, y2, m); break; } } rer(i, y2, y1) { if(divide1(x1, i, x2, y2, m)) { ok |= divide2(x1, y1, x2, i, m); break; } } return ok; } bool divide4(ll x1, ll y1, ll x2, ll y2, ll m) { bool ok = false; rep(i, x1, x2) { if(divide1(x1, y1, i, y2, m)) { ok |= divide3(i, y1, x2, y2, m); break; } } rer(i, x2, x1) { if(divide1(i, y1, x2, y2, m)) { ok |= divide3(x1, y1, i, y2, m); break; } } rep(i, y1, y2) { if(divide1(x1, y1, x2, i, m)) { ok |= divide3(x1, i, x2, y2, m); break; } } rer(i, y2, y1) { if(divide1(x1, i, x2, y2, m)) { ok |= divide3(x1, y1, x2, i, m); break; } } rep(i, 0, H) { rep(j, 0, W) { if(divide1(0, 0, i, j, m)) { int x = 0, y = 0; while(x <= H && !divide1(0, j, x, W, m)) { x++; } while(y <= W && !divide1(i, 0, H, y, m)) { y++; } if(x <= H && y <= W) { if((x <= i && y >= j) || (x >= i && y <= j)) { ok |= divide1(x, y, H, W, m); } } } } } return ok; } void solve() { cin >> H >> W >> N; rep(i, 0, H) { rep(j, 0, W) { ll a; cin >> a; S[i + 1][j + 1] += a + S[i + 1][j] + S[i][j + 1] - S[i][j]; } } ll lv = -1, rv = inf; while(rv - lv > 1) { ll m = (lv + rv) / 2; if(N == 2) { if(divide2(0, 0, H, W, m)) lv = m; else rv = m; } else if(N == 3) { if(divide3(0, 0, H, W, m)) lv = m; else rv = m; } else { if(divide4(0, 0, H, W, m)) lv = m; else rv = m; } } cout << lv << "\n"; }
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646&lang=jp
dp(l, r, k):=区間[l, r)内でトーナメント表を作るとして2^kが優勝するときの最小変更回数
とすれば区間はたかだかO(M*N)個しかないのでO(M*N^2)で計算できて間に合います。1回dp tableがでかくしすぎてMLEした。
こういうの制約が大きいから貪欲的に考えがちだけど、DPにも頭を働かせられるようになるといいですね。
int N, M, K; //K:=num of interval pl I[MAX_N]; pi nex[MAX_N]; int D[MAX_N]; //depth int S[MAX_N]; //-1 or else ll A[10010], B[10010]; ll dp[MAX_N][31]; void init(ll l, ll r, int k, int d) { I[k] = pl(l, r); D[k]= d; int at = upper_bound(A, A + M + 1, l) - A; ll m = (l + r) / 2; if(A[at] >= r) { S[k] = B[at - 1]; } else { S[k] = -1; nex[k] = pi(K + 1, K + 2); K += 2; init(l, m, nex[k].fst, d + 1); init(m, r, nex[k].sec, d + 1); } } ll loop(int at, int s) { if(dp[at][s] != -1) return dp[at][s]; else if(S[at] != -1) { ll l = I[at].sec - I[at].fst; ll sub = 0; if(S[at] > D[at]) { sub = (1LL << (S[at] - (D[at] + 1))); } else if(S[at] <= D[at]) { sub = (s == S[at]); } return l - sub; } else { ll lv = loop(nex[at].fst, s) + loop(nex[at].sec, D[at] + 1); ll rv = loop(nex[at].fst, D[at] + 1) + loop(nex[at].sec, s); return dp[at][s] = min(lv, rv); } } void solve() { cin >> N >> M; rep(i, 0, M + 1) cin >> A[i]; rep(i, 0, M) cin >> B[i]; K = 0; init(0, (1LL << N), 0, 0); memset(dp, -1, sizeof(dp)); cout << loop(0, 0) << "\n"; }