srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.50 おもちゃ箱

問題

問題概要

もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。

解法

すぐbitDPだろうなというのはわかる。ただ、どうやって、実装するかわからん。箱を使う最小値を求めればいいのだから、箱は大きいものから使用していけばいいことは自明。よって、おもちゃを箱に入れていく順番が重要?dpの状態として、いれたおもちゃの集合と大きい箱から何個目の箱までを使ったかをメモっておけば、その集合内で、どのような順番で箱におもちゃを入れたかはそのあとの解に影響を与えることはないので、bitDPできそう?
よくあるbitDP問題は、n=16などであり、(n!)解法の全探索を許さないが、今回はn=10なので、next_permutaionを利用して、おもちゃを使う順番をすべて確かめることができるので、わざわざ、bitDPで集合を考え、使用したおもちゃという集合と何番目までの箱を使ったかを考えて、計算量を減らす必要がない。
bitDPのコツって何だろう。順列を考える必要がなくなるような状態を考えればいいのかな?あと前処理も重要だよね。

ミス

bitDPすこし変えられると、もうわからんくなる。練習せねば、、、
bitDPは順列を考えなくていいように集合をうまく作るように考えていけばできるかな?

コード

全探索

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
int n, m;

int main(void){
    cin >> n;
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    sort(A.begin(), A.end());
    cin >> m;
    vector<int> B(m);
    rep(i, m) cin >> B[i];
    //箱は大きいものから使ったほうがいい
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());

    int ans = INF;
    //商品を入れていく順番をすべて試す (n!)
    do{
        vector<int> hako(m);
        rep(i, m) hako[i] = B[i];
        int tm = 0;//どこ箱まで使ったかをメモするもの
        bool flag = false;

        for (int i = 0; i < n ; ++i){//順番におもちゃを入れていく
            for (int j = 0; j < m; ++j){//箱を大きいものから使っていく
                if(hako[j] - A[i] >= 0){
                    hako[j] -= A[i];//容量を減らす
                    tm = max(tm, j);
                    break;
                }
                if(j == m - 1){
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) continue;//すべての荷物が入っている時のみ、ansを更新
        ans = min(ans, tm);
    }while(next_permutation(A.begin(), A.end()));

    if(ans != INF) cout << ans  + 1 << endl;
    else cout << -1 << endl;
    return 0;
}

bitDP解法、dp配列を集合のみの1次元で書いたらバグが出て、最終的にわからなかった。うーんdpで同じ配列を使いまわすのは難しいなー。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
int n, m;

//dp[i][s] := i番目の箱まで考えて、集合sをすべてを入れるのに使う箱の最小数
int dp[12][(1 << 12)];
//sum[s] := 集合sの荷物の合計値
int sum[(1 << 12)];

int main(void){
    cin >> n;
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    sort(A.begin(), A.end());
    cin >> m;
    vector<int> B(m);
    rep(i, m) cin >> B[i];
    //箱は大きいものから使ったほうがいい
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());

    //選んだ荷物の組み合わせによる荷物の合計を出しておく。
    for (int mask = 0; mask < (1 << n); ++mask){
        int tsum = 0;
        for (int p = 0; p < n; ++p){
            if(mask & (1 << p)){
                tsum += A[p];
            }
        }
        sum[mask] = tsum;
    }

    //dp
    rep(i, 12)rep(j, (1 << 12)) dp[i][j] = INF;
    dp[0][0] = 0;
    for (int i = 0; i < m; ++i){//i番目の箱を考える
        for (int mask1 = 0; mask1 < (1 << n); ++mask1){//i-1番目までの箱に入っている荷物の集合
            if(dp[i][mask1] == INF)continue;//mask1の集合がでi-1番目までの箱を使い入れられていない
            for (int mask2 = 0; mask2 < (1 << n); ++mask2){//mask2集合はi番目の箱にいれようとする荷物
                //同じ位置のbitが立っていない, mask2の集合の荷物がi番目の箱に入る
                if((mask1 & mask2) == 0 && sum[mask2] <= B[i]){
                    dp[i + 1][mask1 | mask2] = min(dp[i + 1][mask1 | mask2], dp[i][mask1] + 1);
                }
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= m; ++i){
        ans = min(ans, dp[i][(1 << n) - 1]);
    }
    if(ans != INF){
        printf("%d\n", ans);
    }else{
        printf("-1\n");
    }
    return 0;
}