AtCoder Beginner Contest 159 E - Dividing Chocolate

E - Dividing Chocolate

記事を移動してきました。

実装が重いと思うのは私の実装力のなさ故でしょうか・・・。反省点としては、通るはずの計算量なのにTLEした場合は、更なる高速化に走る必要はなく、コーナーケースによっては無限ループが生じるということを意識するべきということです。当たり前のことですが、コンテスト中は正気になれないことが多いので気をつけたいです。

E - Dividing Chocolate

問題概要

問題へのリンク

gridを分割し、領域内に $K$ 個以内の $1$ が入ってるようにするために必要な分割回数の最小値を求める問題。

方針

一次元で考えてみる

gridの問題で有効なのが、まずは一次元で考えるという方法です。 $H = 1$ として一次元なら簡単です。Wの配列を前から見ていって $K$ を超えそうになったらそこで分割するという貪欲で解けます。

gridが妙に横長なことに気づく bit全探索

今回はこれが $H$ 次元(最大 $10$ 次元)になったということです。横がひたすら長く、縦が申し訳程度しかありません。これは問題が解かれるようにするためのwriter側の配慮で、実は横方向の分割パターンを前列挙してほしいというお気持ちを読み取ることがポイントです。

横方向の $k$ 番目の区切りを区切るかどうかをbit全探索します。 $H-1$ 個区切りがあるので $2^{H-1}$ を列挙します。これによって横分割が固定できたので、縦をどうしようということになります。

縦割パート

結論から言うと、縦は一次元同様前から貪欲で大丈夫です。前から分割単位での合計の最大値が $K$ を超えないように縦を調整します。

実装パート

実装は煩雑になりがちですが、DPみたいに（？）前から和を更新してもいいですし、2つvectorを持って更新するたびにswapするみたいな方法もありです。最近は勝手にswapにハマっているので（？）、swapで書きました（書きたがり）。メモリ節約のためだという認識でいます。すぬけさんがDPをswapで書いててかっこいいと思ったので採用しています。

コーナーケース

ここまでの処理を書くと実装方法によっては無限ループが生じます。ある列を入れるとどうやってもどこかの分割で合計が $K$ を超えてしまう場合です。これに本番は気づかなかったので、ACできませんでした。パフォ的には300くらい差があるのでかなり悔しいです。

このような列があるときはそれ以上先を見る必要がないのでその横分割パターンはなかったことにして先に進みましょう。

実装

以上のような考察で、 $\mathcal{O}(2^{H-1}H^{2}W)$ で解くことができました。横割りを固定して右端を調べるときに二分探索したり、色々な和を求めるところを累積和で高速化したりという方法も考えられるので、考えてみると面白いです。

ベタ書き実装

提出へのリンク

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define bit(k) (1LL<<(k))
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INFLL = (ll)1e18+1;
int H, W, K;
vector<string> S;
int main() {

    cin >> H >> W >> K;
    S.resize(H);
    rep(i,H)cin >> S[i];
    ll ans = INFLL;
    //境界の状態を全探索
    rep(k,bit(H-1)){
        // l個目の境界が分かれているか
        vector<int> v;
        v.push_back(0); 
        ll cnt = 0; // 境界の本数
        rep(l, H-1){                    
            if(k & bit(l)){
                v.push_back(l+1);
                cnt++;
            }
        }
        v.push_back(H);
        vector<int> counts(int(v.size()-1),0);
        bool ok = true;
        map<int, int> map;
        rep(j,W){
            map[j]++;
            if(!ok)break;
            vector<int> nxt((int)v.size()-1, 0);
            int maxx = 0;
            rep(m, v.size()-1){
                int l = v[m];
                int r = v[m+1];
                //[l,r)行ごとに分ける
                nxt[m] = counts[m];
                //j行目の、[l,r)の足し算
                for(int i = l;i < r;i++){
                    nxt[m] += S[i][j] - '0';
                }
                chmax(maxx, nxt[m]);
            }
            if(maxx <= K){
                swap(counts,nxt);
            }
            else{
                if(map[j] >= 2)ok = false;
                j--;
                counts.assign((int)v.size()-1,0);
                cnt++;
                continue;
            }
        }
        if(ok)chmin(ans, cnt);
    }
    cout << ans << endl;
}

ラムダ式を使ったまとまった実装

（後日談）

今回は非常にループが多く、処理が読みにくいので、処理ごとに分けて実装すると見通しも立ちやすいですしデバッグもしやすいはずです。

今回は

bit全探索
bit表現からvectorになおす処理
横方向の分割が与えられたときの分割の最小値

をそれぞれラムダ式の処理にまとめてみました。かなり読みやすくなったと思います。

また、上では下手だった無限ループが生じないように処理を打ち切る処理も、横方向の長さを計算しながら伸ばしていくことで確認を簡潔にし、返り値にINF（初期値）を設定することで綺麗に実装することができました（渾身のドヤ顔）。

AtCoderでは実装が軽い問題が多く、参加者の実装力に不安がある（？）と公式も言っていたりするので、こういう問題が増えていくかもしれませんね。普段から見通しを立てて綺麗に実装するようにしていきたいものです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define bit(k) (1LL<<(k))
typedef long long ll;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const int INF = (ll)1e9;

int main() {

    // input
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> S(H);
    rep(i,H)cin >> S[i];

    // 区切りのbit表現から縦の領域を表すvectorに変換する
    auto bit2vec = [&](int k){
        vector<int> res;
        res.push_back(0);
        for(int l = 0; l < H-1;l++){
            if(k & bit(l)){
                res.push_back(l+1);
            }
        }
        res.push_back(H);
        return res;
    };
    // ある縦の区切り方のbit表現から区切りの最小値を出力する
    auto mini = [&](int k){
        auto div = bit2vec(k);
        int res = div.size() - 2;
        int m = div.size() - 1;
        int len = 0;
        vector<int> sum(m, 0);
        rep(j,W){
            vector<int> nxt(m, 0);
            int maxx = 0;
            rep(a, m){
                int u = div[a];
                int d = div[a+1];
                nxt[a] += sum[a];
                for(int i = u;i < d;i++){
                    nxt[a] += S[i][j] - '0';
                }
                chmax(maxx, nxt[a]);
            }
            if(maxx <= K){
                len++;
                swap(sum, nxt);
            }
            else{
                if(len == 0)return INF;
                j--;
                sum.assign(m, 0);
                res++;
                len = 0;
            }
        }
        return res;
    };
    
    // 実際の処理
    int ans = INF;
    for(int k = 0; k < bit(H-1);k++){
        chmin(ans, mini(k));
    }

    cout << ans << endl;
}

ながめも

競技プログラミングについて