【ABC159】E - Dividing Chocolate

atcoder.jp

解法

二次元グリッドの問題はHとWの制約が同じことが多いが、この問題はHだけが何故かとても小さい。
あからさまに怪しいのでHの小ささを利用したくなる。

そこで、bit全探索を使って横方向の切り方を全探索することにする。
縦方向の切れ目の入れ方は、チョコを左から見ていって、ブロック内のホワイトチョコがKを超えた時点でその直前に切れ目を入れてやれば良い。

これで、O(2^H HW)で問題を解くことができた。

実装

実装が重めだった。

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<int>> s(H, vector<int>(W));
    REP (i, H) REP (j, W) {
        char ch;
        cin >> ch;
        s[i][j] = ch - '0';
    }

    int ans = INF;

    // 横方向の分割の仕方でbit全探索
    // 縦方向は貪欲で計算
    for (int bit = 0; bit < (1<<(H-1)); bit++) {
        vector<int> S;
        for (int i = 0; i < (H-1); i++) {
            if (bit & (1<<i)) {
                S.push_back(i);
            }
        }

        // siz: 横に分割したときにチョコレートが何個に分かれたか
        // cut: 分割回数
        int siz = S.size()+1, cut = siz-1;
        bool flag = false; // 条件を満たさないときにフラグを立てる
        // cnt[i]: 上からiブロック目のホワイトチョコの数を集計
        vector<int> cnt(siz, 0);

        REP (j, W) {

            int iter = 0;
            // cur[i]: j列目の上からiブロック目のホワイトチョコの数
            vector<int> cur(siz, 0);
            REP (i, H) {
                cur[iter] += s[i][j];

                if (siz-1 > iter && S[iter] == i) iter++;
            }

            bool change = 0; // cutするならchange = 1にする
            REP (i, siz) {
                if (cur[i] > K) flag = 1;

                // Kを超えないならブロックに加算
                if (cur[i] + cnt[i] <= K) cnt[i] += cur[i];
                else change = 1; // 超えるならリセット
            }

            // 切る
            if (change) {
                cut++;
                // ブロックごとの集計をリセット
                REP (i, siz) cnt[i] = cur[i];
            }

            if (flag) break;
        }

        if (!flag) chmin(ans, cut);
    }

    c(ans); // 出力

    return 0;
}