AtCoder ARC #049 : C - ぬりまーす

Cが解けずじまいだった。
http://arc049.contest.atcoder.jp/tasks/arc049_c

問題

N個の頂点に色を塗りたい。
なお、色を順に塗る際以下のルールがある。
タイプ1はA個、タイプ2はB個ある。

• タイプ1: 頂点xに色を塗るとき、頂点yに先に色が塗られていなければならない
• タイプ2: 頂点uに色を塗るとき、頂点vに先に色が塗られていてはいけない

上記ルールの範囲で頂点に順に色を塗るとき、最大何頂点塗れるか。

解法

まずタイプ1だけある場合を考える。
タイプ1が連鎖的にめぐりめぐって「頂点に色を塗るとき、自分自身を先に塗らないといけない」という状況になった点があると、その頂点は塗れない。
またその頂点が先に色を塗られていないと色を塗れない頂点は、連鎖的に色を塗れない。
それら以外の頂点は塗ることができる。

この処理は実質有向グラフの閉路検出なので、強連結成分分解やWarshall-Floyedで行える。
ただWF法だとTLEの懸念がある。

次にタイプ2を考える。
タイプ2の文章を言い換えると、以下のどちらかであると言える。

• 頂点vには色を塗らない
• 頂点vに色を塗るならば、先にuが塗られていないといけない。

後者は実質タイプ1の条件に一致する。

Bの上限は小さいので、タイプ2に対しどちらを取るか2^B通り総当たりしよう。
あとはタイプ1とタイプ2(を2通りのいずれか解釈した条件)の条件からなる有向グラフに対し、上記強連結成分分解及び塗れない頂点を連鎖的に求めればよい。

int N,A,B;
int X[101],Y[101];
int U[101],V[101];
vector<int> E[101];
int NG[101];

class SCC {
public:
	static const int MV = 102;
	vector<vector<int> > SC; int NV,GR[MV],rev[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); rev[cu]=ind;
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

int dodo() {
	SCC scc;
	scc.init(N);
	int i,j;
	FOR(i,N) FORR(r,E[i]) scc.add_edge(i,r);
	scc.scc();
	
	FOR(i,scc.SC.size()) {
		if(scc.SC[i].size()>1) FORR(r,scc.SC[i]) NG[r]=1;
	}
	FOR(i,N) {
		FOR(j,N) FORR(r,E[j]) NG[j]|=NG[r];
	}
	return count(NG,NG+N,0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>A;
	FOR(i,A) {
		cin>>X[i]>>Y[i];
		X[i]--,Y[i]--;
	}
	cin>>B;
	vector<int> C;
	FOR(i,B) {
		cin>>U[i]>>V[i];
		U[i]--,V[i]--;
	}
	
	int ma=0;
	for(int mask=0;mask<1<<B;mask++) {
		ZERO(NG);
		FOR(i,N) E[i].clear();
		int ng=0;
		FOR(i,A) E[X[i]].push_back(Y[i]);
		FOR(i,B) {
			if(mask&(1<<i)) NG[U[i]]=1;
			else E[V[i]].push_back(U[i]);
		}
		if(ng) continue;
		ma=max(ma,dodo());
		
	}
	
	cout<<ma<<endl;
	
	
}

まとめ

うーん、これは思いつかなかった…。