roiti46's blog

主に競プロ問題の解説を載せてます

AOJ 2321: Butterfly

これもpythonで普通のDPをするとTLEしてしまうような問題。BitDPのいい練習となった。 これでこのサイト準拠のAOJ-ICPCの250問題を埋めることができた。

問題

問題はこちら

ある女性は、1日の間にできるだけにたくさんの男性とデートをして満足感を最大にしたい。デート候補の男性は N (≦ 100)人いて、男性iについては、S0時からE0時まで、、、Smi時からEmi時までデートをする予定となっている(6 ≦ Sj, Ej ≦ 22)。つまり一人の男性に対して、複数の時間帯デートをする場合もあるということである。男性iとデートをすれば満足感Liを得ることができる。複数の男性間でデート時間が被っているときは、だれか一人としかデートはできない。この条件下で、女性が得ることのできる満足感の最大値を答える。

解説

1人に対するデート時間が複数あるため、いもす法などでは対応できない。

この問題では、6時から22時それぞれをbitとするようなBitDPを行えばよい。 時間の幅が17しかないため、これで(C++などでは)十分に間に合う。 dp[予定の埋まり方] = (満足度の最大値) として、それぞれの男性について値を更新していけばいい。

時間の幅が17で、nが最大100なので計算量は最大 217*100 > 107 となり、さらに複数個のデータセットがあるためpythonだと制限に間に合わなかった。 普通のdpをしても間に合わないときの代替方法としてdictを使った方法がある。下の解答コードを見てもらえばわかるが、配列を使ったDPとほぼ一緒だが、存在しない予定の組み合わせを調べないことにより高速化している。この方法は計算時間がデータセットに大きく依存するが、この問題だと0.15secとC++などの一部の解答よりもいくらかはやいものとなった。また、dictだとkeyの存在判定が面倒なので、defaultdictで処理を簡潔かつ高速にしている。使ってない人はぜひ使ってみよう。

from collections import defaultdict
while 1:
    n = int(raw_input())
    if n == 0: break
    L = [0]*n
    T = [0]*n
    for man in xrange(n):
        m,l = map(int,raw_input().split())
        L[man] = l
        t = 0
        for date in xrange(m):
            s,e = map(int,raw_input().split())
            t |= 2**(e-6)-2**(s-6)
        T[man] = t

    dp = defaultdict(int)
    for l,t in zip(L,T):
        for bit in dp.keys():
            if bit&t == 0:
                dp[bit|t] = max(dp[bit|t], dp[bit]+l)
        dp[t] = max(dp[t], l)
        
    print max(dp.values())

以下はC++による普通のDP。たいして高速化の工夫をしていないため計算時間は0.87secとなった。こう考えるとdictを使った代替DPはわりと優秀なのかもしれない。

#include <iostream>
#define rep(i,a) for (int i = 0; i < (a); i++)
using namespace std;

int n, m, l, s, e;
int L[100], T[100], dp[1 << 17];

int main(void){
    while (cin >> n, n) {
        rep(i, 1 << 17) dp[i] = 0;
        rep(i, n) {
            cin >> m >> l;
            L[i] = l;
            int t = 0;
            rep(j, m) {
                cin >> s >> e;
                t |= (1 << (e-6)) - (1 << (s-6));
            }
            T[i] = t;
        }
        
        int mx = 1;
        rep(i,n) {
            rep(bit, mx) {
                if ((bit & T[i]) == 0 && dp[bit]) {
                    dp[bit | T[i]] = max(dp[bit | T[i]], dp[bit] + L[i]);
                    mx = max(mx, (bit | T[i]) + 1);
                }
                dp[T[i]] = max(dp[T[i]], L[i]);
                mx = max(mx, T[i]+1);
            }
        }
        int ans = 0;
        rep(i, 1 << 17) ans = max(ans, dp[i]);
        cout << ans << endl;
    }
    return 0;
}