国内予選出るので精進します。
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) {
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) {
return get(x1, y1, x2, y2) >= m;
}
bool divide2(int x1, int y1, int x2, int y2, ll m) {
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) {
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;
pl I[MAX_N];
pi nex[MAX_N];
int D[MAX_N];
int S[MAX_N];
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";
}