AtCoder ABC 159

March 23, 2020

A	B	C	D	E	F
o	o	o	o	x	x

A~Dは特に問題なく解けた。Eは考察軽め、実装重めの問題。解法はわりとすぐに思いついたが、実装間に合わず。あまり得るものがなく、実装力不足のみを痛感させられた。

E

二次元累積和を事前に計算して、ブロックの範囲が与えられたときに、そのブロックに含まれる1がK個以下かどうかを判定するという方針で実装した。

#define MAX_H 10
#define MAX_W 1'000
#define INF 1152921504606846976
i64 H, W, K;
i64 G[MAX_H][MAX_W];
i64 C[MAX_H + 1][MAX_W + 1];

i64 count(i64 y1, i64 x1, i64 y2, i64 x2) {
    return C[y2][x2] - C[y2][x1] - C[y1][x2] + C[y1][x1];
}

int main() {
    cin >> H >> W >> K;
    char c;
    REP(y, H) REP(x, W) {
        cin >> c;
        G[y][x] = c - '0';
    }

    REP(y, H + 1) REP(x, W + 1) C[y][x] = 0;
    REP(y, H) REP(x, W) {
        C[y + 1][x + 1] = C[y][x + 1] + C[y + 1][x] - C[y][x] + G[y][x];
    }

    i64 min_n = 10000000000;
    REP(bit, 1 << (H - 1)) {
        vector<i64> div_y;
        div_y.reserve(H);
        REP(y, H) {
            if (bit >> y & 1) {
                div_y.pb(y + 1);
            }
        }
        div_y.pb(H);

        i64 n_col = 1;
        i64 x1, x2;
        for (x1 = 0, x2 = 1; x2 <= W; x2++) {
            bool ok = true;

            i64 y1, y2;
            y1 = 0;
            for (auto y2 : div_y) {
                if (count(y1, x1, y2, x2) > K) ok = false;
                y1 = y2;
            }

            if (!ok) {
                if (x2 - x1 == 1) {
                    n_col = INF;
                    break;
                }
                x1 = x2 - 1;
                n_col++;
            }
        }

        if (n_col < INF) {
            chmin(min_n, n_col - 1 + SIZE(div_y) - 1);
        }
    }
    cout << min_n << endl;

    return 0;
}