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
この記事が気に入ったらサポートをしてみませんか?