AtCoder ABC 159 E - Dividing Chocolate (1Q, 水色, 500 点)

制約が縦方向の bit 管理を要求している感満載

問題へのリンク

問題概要

のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。

これを実現できるような、ラインの本数の最小値を求めよ。

制約

• 
• 

考えたこと

縦横両方を考えるのは大変なので、どちらかを固定したくなる...と思っていたところに、 という制約が飛び込んできた。これはもう

• 横のラインの引き方 ( 通りある) を決め打ちして全探索せよ

ということだ。ここまで思うともう簡単で、縦のラインは、Greedy でよい。つまり、

• 最後に縦のラインを引いた地点から
• を超えないギリギリのところまで引っ張って
• 限界を超える手前でラインを引く

という風な Greedy で OK。ギリギリまで引っ張ることをせずに縦のラインを引く意味はないからだ。計算量は [tex: O(2^H HW)]。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int H, W, K;
vector<string> fi;

int solve() {
    int res = 1<<29;
    for (int bit = 0; bit < (1<<(H-1)); ++bit) {
        bool gok = true; // そもそも不可能な場合もあるので判定
        int N = 0;
        vector<int> ord(H, 0);
        for (int i = 0; i < H-1; ++i) {
            if (!(bit & (1<<i))) ord[i+1] = ord[i];
            else ord[i+1] = ord[i]+1, ++N;
        }
        int add = 0;
        vector<int> nums(N+1, 0);
        for (int w = 0; w < W; ++w) {
            vector<int> one(N+1, 0);
            bool ok = true;
            for (int h = 0; h < H; ++h) {
                one[ord[h]] += fi[h][w] - '0';
                nums[ord[h]] += fi[h][w] - '0';
                if (one[ord[h]] > K) gok = false;
                if (nums[ord[h]] > K) ok = false;
            }
            if (!ok) ++add, nums = one;
        }
        if (gok) chmin(res, N + add);
    }
    return res;
}

int main() {
    cin >> H >> W >> K;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    cout << solve() << endl;
}