天下一プログラマーコンテスト2012 予選A / C - 敵対的引用

C: 敵対的引用 - 天下一プログラマーコンテスト2012 予選A | AtCoder

問題

有向グラフA(V<=10^5, E<=10^4)が与えられ、また、その補グラフBを考える。
ある一ノードpとbool配列x[N](N<=150くらい)が与えられた時、
pから出発してi番目(i

• x[i]がtrueならAを進むことができ、
• x[i]がfalseならBを進むことができる。

この時、到達可能なノードの数を答えよ。

回答

(i-1)番目の状態からi番目の状態(到達可能かどうか)を作る。
falseの時は、前回までに到達可能なノードの全てが自分へ向かうエッジを持っているとfalseであって、
それは到達可能な中で自分へ向かうエッジの数と全ての到達可能の数が違えばいい。

コメント

人の回答を参考にした。
全てのXがYであると駄目、という時にXの数とYの数を数えて比較、というのはありだ。覚えておこう。
本番では変な考え方してそのまま時間が過ぎてしまった。普通に色々な状態を考えて考えよう。
後から考えると非常に簡単に思えるので、このくらいはパース含めて20分くらいで解きたいと思う

コード

#define _GLIBCXX_DEBUG
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);(i)++)
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);(i)++)
#if defined(_MSC_VER)
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it,o.begin()); it != (o).end(); it ++)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii;

#define INF 0x3f3f3f3f

int e[10001],r[10001];
char s[350];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	rep(i,m){
		int x,y;
		scanf("%d%d",&x,&y);
		x--;y--;
		e[i]=x;r[i]=y;
	}
	scanf("%s",s);
	int l = strlen(s);
	bool a[150]={0};
	int c=1;
	int t=-1; bool ta;
	function<int(int)>f;
	f=[&](int i)->int{
		if(s[i]=='"'){
			i = f(i+1);
			++i;
			a[c] = s[i]=='w'?(i+=2,true):false;
			c++;
			return i;
		}else{
			i+=5;
			int x,n;
			sscanf(s+i,"%d%n",&x,&n);
			x--;
			i+=n;
			t = x;
			if(s[i]=='w'){
				i++;
				ta=true;
			}else ta=false;
			return i;
		}
	};
	f(0);
	static bool d[151][100001];
	mset(d[0], 0);
	a[0] = ta;
	d[0][t] = true;
	rer(i,1,c){
		if(a[i-1]){
			//誰かを敵対視しているとtrue
			fill(d[i],d[i]+n, false);
			rep(j, m) {
				d[i][e[j]]|=d[i-1][r[j]];
			}
		}else {
			//誰かを敵対視していない、つまり、
			//敵対視している人が全て1であると駄目
			fill(d[i],d[i]+n, false);
			static int x[100001];
			int y=0;
			mset(x,0);
			rep(j,n)y+=d[i-1][j];
			rep(j, m) {
				x[e[j]]+=d[i-1][r[j]];
			}
			rep(j,n){
				d[i][j]=x[j]!=y;
			}
		}
	}
	int r=0;
	rep(i,n)r+=d[c][i];
	printf("%d\n",r);
	return 0;
}