Codeforces #1030 : Div2 D2. Red Light, Green Light (Hard version)

あまり出来の良くなかった回。
https://codeforces.com/contest/2118/problem/D2

問題

N個のマスが一列に並んでいる。
各マスには、周期Kの信号があり、各マス時刻Kごとに赤信号が点灯する。
初回点灯するタイミングはマスごとにバラバラで、入力として与えられる。

以下のクエリに順次答えよ。

• プレイヤーは初期状態でマスQにいて、正方向を向いている。
  • 時刻1ごとに向いている方向に1マス移動する。移動後のマスがちょうど赤信号が点灯していた時、向きを反転する。

そのうちプレイヤーは、Nマス外に移動するか判定せよ。

解法

2N点の有向グラフを考える。
各点は、各マスで左または右から侵入して向きを反転するケースに相当する。

まず、各マスで反転した際、次にどこで反転するかを求めよう。
そのような2マスに対応して、グラフに有向辺を張る。
もしこのグラフが閉路を持つ場合、その通りプレイヤーが移動するとNマス外に移動できないことになる。

各クエリに対し、初回反転するマスを二分探索などで求め、それが閉路の一部であるか判定すればよい。

int T;
ll N,K;
ll P[202020],D[202020],R[202020],L[202020];
int Q;
ll A[202020];

class SCC {
public:
	static const int MV = 2025000;
	vector<vector<int> > SC; int NV,GR[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<NV;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);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		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);
	}
};
SCC scc;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<402020> uf;
int loop[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) {
			cin>>P[i];
		}
		FOR(i,N) {
			cin>>D[i];
			L[i]=((D[i]-P[i])%K+K)%K;
			R[i]=((D[i]-((1LL<<50)-P[i]))%K+K)%K;
		}
		scc.init(2*N);
		uf.reinit(2*N);
		FOR(i,2*N) loop[i]=0;
		
		map<ll,int> V;
		FOR(i,N) {
			if(V.count(R[i])) {
				scc.add_edge(2*i,2*V[R[i]]+1);
				uf(2*i,2*V[R[i]]+1);
			}
			V[R[i]]=i;
		}
		V.clear();
		set<pair<ll,ll>> Vs;
		for(i=N-1;i>=0;i--) {
			if(V.count(L[i])) {
				scc.add_edge(2*i+1,2*V[L[i]]);
				uf(2*i+1,2*V[L[i]]);
			}
			V[L[i]]=i;
			Vs.insert({L[i],P[i]});
		}
		Vs.insert({K,0});
		scc.scc();
		FOR(i,scc.SC.size()) {
			if(scc.SC[i].size()>1) {
				loop[uf[scc.SC[i][0]]]=1;
			}
		}
		
		
		cin>>Q;
		FOR(i,Q) {
			ll A,AL;
			cin>>A;
			AL=(((-A)%K)+K)%K;
			auto it=*Vs.lower_bound({AL,A});
			if(it.first!=AL) {
				cout<<"YES"<<endl;
				continue;
			}
			x=lower_bound(P,P+N,it.second)-P;
			if(loop[uf[x*2]]) {
				cout<<"NO"<<endl;
			}
			else {
				cout<<"YES"<<endl;
			}
		}
	}
}

まとめ

一見コード量は多いけど、やることはそこまで難しくはない。