TopCoderOpen 2021 Round2A : Medium TheUltimatePackages

格別いい出来ではなかったが、Parallelなせいか？結構レートが増えた。
https://community.topcoder.com/stat?c=problem_statement&pm=16985&rd=18683

問題

N点D辺の有向グラフが与えられる。
辺の向きは、常に頂点番号の小さい方から大きい方に向かうものとする。

究極の頂点vとは、他の全頂点uに対し、uから辺に沿ってvに到達可能か、vから辺に沿ってuに到達可能のいずれかであることを意味する（どちらも到達できないような頂点がない）。
グラフにおける究極の頂点vを列挙せよ。

解法

頂点数が多いので、bitsetでO(N^2)分の配列をもって到達可能性を管理しようとするとTLEする。
そこで別解を考えよう。
究極の頂点にならないことが確定した点を数え上げることを考える。
今頂点vについて考えよう。
vに向けて辺を張る頂点のうち、番号が最大のものとsとし、vから辺が出ている先の頂点のうち、番号が最小のものをtとしよう。
(s+1)～(v-1)からvには辺にそって到達できないし、vから(v+1)～(t-1)には到達できない。
よってこれらの頂点は究極の頂点の候補から外そう。

s未満の点やt+1以降の点は考えなくて良いのか？となるが、s未満に究極の頂点があれば、それはs経由でvに到達可能なので考えなくてよい。t+1以降の点も同様。

vector<int> E[66666],RE[66666];

int NG[65656];

class TheUltimatePackages {
	public:
	vector <int> count(int N, int D, vector <int> Xprefix, vector <int> Yprefix, int L, int seed) {
		vector<ll> X(D), Y(D);
		int XL = Xprefix.size();

		for (int i=0; i<XL; ++i) {
		    X[i] = Xprefix[i];
		    Y[i] = Yprefix[i];
		}

		long long state = seed;
		for (int i=XL; i<D; ++i) {
		    state = (state * 1103515245 + 12345) % (1LL << 31);
		    int elen = 1 + state%L;
		    state = (state * 1103515245 + 12345) % (1LL << 31);
		    Y[i] = state % (N - elen);
		    X[i] = Y[i] + elen;
		}
		int i;
		FOR(i,N) E[i].clear(),RE[i].clear();
		FOR(i,D) {
			E[X[i]].push_back(Y[i]);
			RE[Y[i]].push_back(X[i]);
		}
		ZERO(NG);
		
		FOR(i,N) {
			E[i].push_back(-1);
			RE[i].push_back(N);
			sort(ALL(E[i]));
			sort(ALL(RE[i]));
			int L=E[i].back();
			int R=RE[i][0];
			NG[L+1]++;
			NG[i]--;
			NG[i+1]++;
			NG[R]--;
		}
		
		
		vector<int> ret(2);
		FOR(i,N) {
			if(i) NG[i]+=NG[i-1];
			if(NG[i]==0) {
				ret[0]++;
				ret[1]+=i;
			}
		}
		return ret;
	}
}

まとめ

ちょっと自信持てなかったけど、通ってよかった。