TopCoder SRM 703 Div1 Easy DAGConstruction

これもすんなり。
https://community.topcoder.com/stat?c=problem_statement&pm=14457

問題

N頂点の有向グラフのうち、以下の条件を満たすものが作れるか。
作れるなら一例を示せ。

• 各頂点iにはパラメータX[i]が与えられる。
• 各頂点iを始点としたとき、有向辺にそって移動可能な頂点数はX[i]である。

解法

いろいろ解法はありそうだが、以下自分の解法を紹介。

X[i]の小さい順に辺を張る先を決めていく。
mask[i]を頂点iから到達可能な頂点番号のbitmapとする。

これからi番の頂点がどこに辺を張るか考えるとする。
すでに辺を張る先が確定した頂点群jのうち、X[j]の多い順にi→jで辺を張るか判定する。
もしmask[i] | mask[j]のbitcountがX[i]を超えないならi→jに辺を張る、という処理を繰り返す。
すべてのjに対し処理を行っても、mask[i]のbitcountがX[i]に到達しないなら、解なし。

上記のようにすると、すでに辺を張った頂点がM個あるとき、0～M個任意の個数の頂点に到達可能なように辺が張れる。
(mask[i] | mask[j]のbitcountがX[i]を超えてしまう場合、i→jに辺を張ることをあきらめる代わり、jから直接辺が張られているすべての頂点kに対しi→kと辺を張ればmask[i] | mask[k]のbitcountはmask[i] | mask[j]より1小さくなる。)

class DAGConstruction {
	public:
	int N;
	vector <int> construct(vector <int> X) {
		ll mask[51]={};
		vector<int> ret,V;
		vector<pair<int,int>> P;
		N=X.size();
		int i;
		
		FOR(i,N) {
			mask[i]=1LL<<i;
			P.push_back({X[i],i});
		}
		sort(ALL(P));
		FORR(e,P) {
			FOR(i,V.size()) {
				int t=V[V.size()-1-i];
				if(__builtin_popcountll(mask[e.second] | mask[t]) <= X[e.second]) {
					mask[e.second] |= mask[t];
					ret.push_back(e.second);
					ret.push_back(t);
				}
			}
			V.push_back(e.second);
			if(__builtin_popcountll(mask[e.second]) < X[e.second]) return {-1};
		}
		return ret;
	}
}

まとめ

Easyで構築ゲー出すの怖いので勘弁してほしい…。