SRM 388 500pt: InformFriends

TopCoder

問題概要

N(<=15)人の集団がいる。その集団の中で友好関係に関して無向グラフが形成されている。いま、あなたは一人につき一つの情報を流す。情報を受け取った人は自分の直接の友人にのみその情報を伝える。このとき推移的に伝搬はしない。全員が持っている情報の数を最大化する問題。

考えたこと

  • 問題文がよく分からない…。
  • やっと理解した。このままじゃよく分からんので抽象化する。
  • グラフの問題に落としたら支配集合のことだと気付いた。
  • つまり交わらない支配集合を最大いくつ作ることができるか、ということか。
  • サイズ15とかだし、ビットDPが見える。
  • 前処理で支配集合を全て列挙しておけば行けそう。
  • いやちょっと待て。完全グラフだと支配集合の個数が2^Nで、全体の計算量がO(4^N)でTLEだ。
  • どうしよう。とはいえ2^30くらいなら枝刈りで通りそう。
    • 普段は枝刈りで幸せになることは多くないけど。
  • 極小でない支配集合は明らかに使う必要がないので、極小支配集合だけを列挙すると…？
  • どれくらいになるのか具体的には見積もれないけど、流石にこれは効くはずだ。
  • 極小支配集合の列挙も一つビットが増えたところをチェックしておけばよいのでこれまたビットDPっぽく書けそう。
  • スーパーセットに配るビットDPなので順番を気にせず単純なループで書ける。
  • 書けた。一発コンパイルで無事通った。

practiceで通ったコード

計算量がよく分からない…。極小支配集合列挙する部分に関してはO(2^N * N^2)。
極小支配集合の個数をMとすると、ビットDPの部分はO(2^N * M)。

#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 15;

bool visited[MAX_N];
bool is_dominate[1<<MAX_N];
int dp[1<<MAX_N];

struct InformFriends {

	int maximumGroups(vector <string> friends) {
		const int N = friends.size();

		//極小支配集合を全部列挙する
		vector<int> dominates;
		for(int bit=0; bit<(1<<N); bit++){
			if(is_dominate[bit]){
				//もしbitが支配集合なら、それに何か加えたものも支配集合
				for(int i=0; i<N; i++){
					is_dominate[ bit | (1<<i)] = true;
				}
			}
			else{
				//bitが(極小)支配集合かどうか判定する
				memset(visited, 0, sizeof(visited));
				for(int i=0; i<N; i++)if( (bit>>i)&1 ){
					for(int j=0; j<N; j++)if( i==j || friends[i][j] == 'Y'){
						visited[j] = true;
					}
				}

				//全部支配した？
				if( !count(visited, visited+N, false) ){
					is_dominate[ bit ] = true;
					for(int i=0; i<N; i++){
						is_dominate[ bit | (1<<i)] = true;
					}
					dominates.push_back( bit );
				}
			}
		}

		//ビットDP
		for(int bit=0; bit<(1<<N); bit++){
			for(int i=0; i<(int)dominates.size(); i++){
				int next_bit = bit | dominates[i];
				if( (bit ^ dominates[i]) == next_bit ){ //互いに交わらないとき
					dp[next_bit] = max(dp[next_bit], dp[bit] + 1 );
				}
			}
		}

		return *max_element(dp, dp+(1<<N));
	}

};