C - 席が足りない

[Q] https://atcoder.jp/contests/tenka1-2012-qualB/tasks/tenka1_2012_7
bitDPと、補集合の全探索でO(3^N)

Q. bitDP?
A. DP[bit] = 必要な席の数で管理します。
DP[(1<<N)-1] が解答です。

1. DP[bit] = 1を自力で探す。
2. 補集合を用いて全探索。O(3^N)になるらしい。

入力例3
4
00:00 07:00
06:00 13:00
12:00 19:00
18:00 25:00

・DP[bit] = 1を自力で探します。

1人に独占させれば1だし、
DP[0001] = 1 // 1人目を割り当てるのに必要な席の数
DP[0010] = 1 // 2人目を割り当てるのに必要な席の数
DP[0100] = 1 // 3人目を割り当てるのに必要な席の数
DP[1000] = 1 // 4人目を割り当てるのに必要な席の数

1と3、2と4のペアは成立します。
DP[0101] = 1 // 1,3人目を割り当てるのに必要な席の数
DP[1010] = 1 // 2,4人目を割り当てるのに必要な席の数

・それ以外のDPを、補集合を使って求めます。
0001 ~ 1111までbitを動かしつつ、補集合を全探索します。

・i=0001 は次の7パターンを更新
DP[1111] = DP[0001]+DP[1110]
DP[1101] = DP[0001]+DP[1100]
DP[1011] = DP[0001]+DP[1010]
DP[1001] = DP[0001]+DP[1000]
DP[0111] = DP[0001]+DP[0110]
DP[0101] = DP[0001]+DP[0100]
DP[0011] = DP[0001]+DP[0010]

・i=0010 ~ 1111として、
DP[i|op] = min(DP[i|op], DP[i]+DP[op])
を実行します。

DP[0011] = 2 // 1,2人目を割り当てるのに必要な席の数
DP[0110] = 2 // 2,3人目を割り当てるのに必要な席の数
DP[0111] = 2 // 1,2,3人目を割り当てるのに必要な席の数
DP[1001] = 2 // 1,4人目を割り当てるのに必要な席の数
DP[1011] = 2 // 1,2,4人目を割り当てるのに必要な席の数
DP[1100] = 2 // 3,4人目を割り当てるのに必要な席の数
DP[1101] = 2 // 1,3,4人目を割り当てるのに必要な席の数
DP[1110] = 2 // 2,3,4人目を割り当てるのに必要な席の数
DP[1111] = 2 // 1,2,3,4人目を割り当てるのに必要な席の数

DP[1111]=2が解答。

Q. 10:00 を時間と分で受け取りたい
A. 可能でした。

// 10:00

ll h, m;
char c;
cin >> h >> c >> m;

// h=10, c=:, m=0

実装。

bool B[15][15]; // B[a][b]=true : aとbは同じ席に配置できる
ll DP[1<<15]; // DP[bit]=必要な席数

int main(){
 cincout();
 
 ll N;
 cin >> N;
 vector<pll> P(N); // {始業時間, 終業時間}
 rep(i, N){
   rep(j, 2){
     ll a, b;
     char c;
     cin >> a >> c >> b;
     if(j==0) P[i].first = a*60+b;
     else P[i].second = a*60+b;
   }
 }
 sort(all(P));
 rep(i, N){
   for(ll j=i+1; j<N; ++j){
     // ijijならペアできない iijjはできる
     if (P[j].first < P[i].second) continue;
     // jijiならペアできない jjiiはできる
     if (P[i].first+24*60 < P[j].second) continue;
     B[i][j] = true; // ペアok
     B[j][i] = true;
   }
 }
 rep(i, (1LL<<N)){
   bool ok=true;
   rep(j, N) {
     if (((i>>j) & 1) == 0) continue;
     for(ll k=j+1; k<N; ++k) {
       if(((i>>k) & 1) == 0) continue;
       if (!B[j][k]) ok=false;
       if(!ok) break;
     }
     if(!ok) break;
   }
   if(ok) DP[i] = 1;
   else DP[i] = oo;
 }
 
 rep(i, (1LL<<N)){
   ll all = (1LL<<N)-1;
   ll op = i^all;
   for(ll x=op; x>0; x=(x-1)&op){
     chmin(DP[i|x], DP[i] + DP[x]);
   }
 }
 
 cout << DP[(1<<N)-1] << endl;
}

Q. 補集合DP？
A.
for(ll b=op; b>0; b=(b-1)&op)
どうもこの書き方のようです。もれなく探索できるので、こういうもの。

Q. O(3^N)?
A.
補集合を取る箇所で、処理数をカウントアップさせてみる。

N=1, cnt=1 (3^1=3) - 2^1
N=2, cnt=5 (3^2=9) - 2^2
N=3, cnt=19 (3^3=27) - 2^3
N=4, cnt=65 (3^4=81) - 2^4
N=5, cnt=211 (3^5=243)
N=6, cnt=665 (3^6=729)
N=7, cnt=2059 (3^7=2187)
N=8, cnt=6305 (3^8=6561)
N=9, cnt=19171 (3^9=19683)
N=10,cnt=58025 (3^10=59049)

たしかにO(3^N)だった。

https://atcoder.jp/contests/tenka1-2012-qualB/submissions/26074688