SRM 636 Div2 Hard ChocolateDivid

SRM 636 Div2 Hard ChocolateDivid を本番で通せなかったので復習.

問題

長方形の格子状のチョコレートが与えられる.
それぞれのマスには0から9の数値が割り当てられる.
このチョコレートを水平に3カット,垂直に3カットして16個の領域に分割する.
それぞれの分割された長方形の値はその格子内に含まれている値の和とする.
この時,分割された長方形の値の最小値を最大にしたい.
格子の縦,幅 <= 75

(例)
f:id:tatanaideyo:20141015002602p:plain

方針1

与えられる格子の縦をH,幅をWとする.
方針1は全探索と累積和

水平方向のカットの仕方の場合の数 =  \binom{H}{3}
垂直方向のカットの仕方の場合の数 =  \binom{W}{3}

なので,分割の仕方の総数は
 \binom{H}{3} \times \binom{W}{3}
通りある.

それぞれの,分割に対して分割された長方形の中で最小の値を求める.

長方形内に含まれる値の和を愚直にやると最大で H \times W個の領域を見る.
これを定数時間で求める方法に累積和がある.

下の(1)のような長方形が与えられたときに,
配列に(2),(3)のような和を累積していく.
その結果,配列(h, w)の値は(0, 0)を左上,(h, w)とした長方形の値に等しい.

(4)の赤色の長方形の値が知りたい場合は,
緑色の長方形の値(19) - 水色の長方形の値(5)- 黄色の長方形の値(4)+ 橙色の長方形の値(1)
となる.

f:id:tatanaideyo:20141015005551p:plain

このように,前処理を行っておくことによってすべての部分長方形の値を定数時間で求めることができる.

この方針1では最大で
 \binom{75}{3} \times \binom{75}{3} \times 16 = 7.3 \times 10^10
かかるので間に合わない.

方針2

Condition(x) := 最小の値がx以上となる分割が存在するならtrue, 存在しないならfalse
としてxの値を二分探索で求める.

xは高々  \log_{2}(75 * 75 * 9) = 15.2 であるので
Combination(x) の確認が早ければ問題を解くことが出来る.

Combination(x) ではまず,水平方向の分割をすべて行う.
そして,それぞれの分割に対して次の操作で垂直方向の分割を行っていく.
ある水平方向の分割をa, b, cとして垂直方向の操作を下の図でおこなう.

left = 0, r = left + 1で初期化する.
leftとrで囲まれた長方形の値をx1, x2, x3, x4とする.
(1)それぞれの値がx以上ならば,left = r, r = left + 1として同様に確認をおこなう.
(2)x1, x2, x3, x4のうちひとつでもxより小さければrの値を1増やして同様に確認をおこなう.
(1)の操作を4回以上行えればCombination(x)はtrueとなる.
f:id:tatanaideyo:20141015012922p:plain

Combination(x)では高々 \binom{H}{3} \times Hの操作しか行わないので,
合計で,
 \log_{2}(75 * 75 * 9) \times \binom{75}{3} \times 75 = 7.9 \times 10^7
の計算で求められる.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <cmath>
#include <cstring>
#include <climits>
#include <unordered_set>

typedef long long ll;

using namespace std;

class ChocolateDividingHard {
    int H, W;
    int sum[80][80];
public:
    int findBest(vector <string> chocolate) {
        H = chocolate.size();
        W = chocolate[0].size();

        memset(sum, 0, sizeof(sum));

        // 累積和の計算
        for (int i = 1; i <= H; ++i)
            for (int j = 1; j <= W; ++j)
                sum[i][j] += sum[i][j - 1] + (int)(chocolate[i - 1][j - 1] - '0');
        for (int j = 1; j <= W; ++j)
            for (int i = 2; i <= H; ++i)
                sum[i][j] += sum[i - 1][j];

        int lb = 0, ub = sum[H][W];
        while (ub - lb > 1) {
            int mid = (lb + ub) >> 1;

            if (Condition(mid))
                lb = mid;
            else
                ub = mid;
        }

        return lb;
    }

    // 最小の値がx以上となる分割が存在するならtrue
    bool Condition(int x) {
        // 縦に上からa, b, c行目で分割
        for (int a = 1; a <= H; ++a)
            for (int b = a + 1; b <= H; ++b)
                for (int c = b + 1; c <= H; ++c) {
                    int left = 0, cnt = 0;

                    // 列の左から分割していく
                    for (int r = 1; r <= W; ++r) {
                        int x1 = sum[a][r] - sum[a][left];
                        int x2 = sum[b][r] - sum[b][left] - sum[a][r] + sum[a][left];
                        int x3 = sum[c][r] - sum[c][left] - sum[b][r] + sum[b][left];
                        int x4 = sum[H][r] - sum[H][left] - sum[c][r] + sum[c][left];

                        if (x1 >= x && x2 >= x && x3 >= x && x4 >= x) {
                            ++cnt;
                            left = r;
                        }
                    }

                    // それぞれの四角形の和がx以上となるように分割した時に
                    // 分割が4以上ならtrue
                    if (cnt >= 4)
                        return true;
                }

        return false;
    }
};