kmjp's blog

競技プログラミング参加記です

みんなのプロコン予選 : E - 遊園地

その他コンテスト

このテクは知らないので今回は解けなくてもしょうがないか。
http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_e

問題

N個のアトラクションがある遊園地がある。
各遊具は１列に並んでおり、隣の遊具に移動するには体力を1消費する。
各遊具iは体力がL[i]以上あるときに遊ぶことができ、遊んだあとの体力はR[i]になる（増加するケースもある）。

初期状態で無限の体力があるとする。最適にアトラクションを選ぶ場合、最大何個のアトラクションを遊ぶことができるか。

解法

あるアトラクションiのあとにjを遊べる、という関係を有向辺で結んだグラフを考える。
このグラフにおいて、ある頂点から初めて辺をたどり到達可能な頂点数が最大なパスを求めれば、それが求める解となる。
そのためには、グラフを強連結成分分解してDAGに縮約し、トポロジカルソートしてDPいけばよい。

ただ、問題は上記辺を愚直に処理すると辺がO(N^2)個になることである。
そこで、先日のARCのテクを応用して辺を減らそう。
AtCoder ARC #069 : F - Flags - kmjp's blog
すなわち、SegTreeの要領で連続区間のアトラクション(に相当する頂点)に到達可能な頂点を作ることで、個々のアトラクション(に相当する頂点)に辺を張ることを回避する。
上記問題と異なるのは、SegTree上の各頂点の接続先がしばしば変更されることである。
これは永続データ構造の要領で、SegTree上の頂点の接続先が変化する場合、元の頂点を残して新しい頂点を生成することで対応できる。
この新しい頂点の生成はSegTreeの最上位まで伝搬する。

i＞jの場合、アトラクションi→jに辺を張るケースを考える。
i→jに辺を張るには、R[i]-(i-j)≧L[j]ならばよく、移行するとR[i]-i≧L[j]-jと左右i,jだけの式になる。
そこでA[x]=L[x]-x、B[x]=R[x]-xと置き、A[x]、B[x]を合わせて昇順に並べよう。(ただしA[x]==B[y]ならxがyの前に処理されるようにする)
それぞれ以下のように処理する。

  • A[x]を処理する場合
    • 今後A[x]≦B[y]、x＜yとなるyがあれば、y→xに辺を張ることになる。
    • よって、SegTreeの最下段におけるx番の頂点に相当する点から、xに相当する点に辺を張ろう。以後、B[y]を処理する際はこの点(またはこの点を含むような上位の点)に辺を張ることで、間接的にA[x]に辺を張れる。
    • その際、上記記載の通り頂点を生成しながら接続先を更新していくため、O(logN)個点が生成される。
  • B[y]を処理する場合
    • x∈[0,y)において、A[x]が処理済みの頂点群に辺を張りたい。これはSegTree上で区間[0,y)を覆うようなO(logN)個の頂点に辺を張ればよい。

あとは上に書いた通り、こうしてできたグラフを強連結成分分解してDAGに縮約し、トポロジカルソートしていけばよい。

const int MV = 1<<22;

class SCC {
public:
	
	vector<vector<int> > SC; int NV,GR[MV],rev[MV];
	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]]){
			revdfs(NUM[i],c);  c++;
		}
	}
};

int N,NV;
int L[505050],R[505050];
int CV[505050];

SCC sc;
void add(int c,int x,int y,int l=0,int r=1<<16,int k=1) { // x<=i<y
	if(x>=y) return;
	if(r<=x || y<=l) return;
	if(x<=l && r<=y) {
		sc.add_edge(c,CV[k]);
	}
	else {
		add(c,x,y,l,(l+r)/2,k*2);
		add(c,x,y,(l+r)/2,r,k*2+1);
	}
}

set<int> E[MV];
int num[MV];
int ma[MV];
int in[MV];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	FOR(i,N) cin>>R[i];

	vector<pair<int,int>> V,V2;
	sc.init(MV);
	NV=N;
	FOR(i,N) {
		V.push_back({L[i]-i,i});
		V.push_back({R[i]-i,i+N});
		V2.push_back({L[i]+i,i});
		V2.push_back({R[i]+i,i+N});
	}

	sort(ALL(V));
	FOR(i,1<<16) CV[(1<<16)+i]=NV++;
	for(i=(1<<16)-1;i>=1;i--) {
		CV[i]=NV++;
		sc.add_edge(CV[i],CV[2*i]);
		sc.add_edge(CV[i],CV[2*i+1]);
	}
	FORR(e,V) {
		if(e.second<N) {
			x = e.second+(1<<16);
			CV[x]=NV++;
			sc.add_edge(CV[x],e.second);
			while(x>1) {
				x/=2;
				CV[x]=NV++;
				sc.add_edge(CV[x],CV[x*2]);
				sc.add_edge(CV[x],CV[x*2+1]);
			}
		}
		else add(e.second-N,0,e.second-N);
	}
	sort(ALL(V2));
	FOR(i,1<<16) CV[(1<<16)+i]=NV++;
	for(i=(1<<16)-1;i>=1;i--) {
		CV[i]=NV++;
		sc.add_edge(CV[i],CV[2*i]);
		sc.add_edge(CV[i],CV[2*i+1]);
	}
	x=0;
	FORR(e,V2) {
		if(e.second<N) {
			x = e.second+(1<<16);
			CV[x]=NV++;
			sc.add_edge(CV[x],e.second);
			while(x>1) {
				x/=2;
				CV[x]=NV++;
				sc.add_edge(CV[x],CV[x*2]);
				sc.add_edge(CV[x],CV[x*2+1]);
			}
		}
		else add(e.second-N,e.second-N+1,N);
	}
	sc.NV=NV;
	sc.scc();
	FOR(i,NV) {
		if(i<N) num[sc.GR[i]]++;
		FORR(e,sc.E[i]) if(sc.GR[i]!=sc.GR[e]) E[sc.GR[i]].insert(sc.GR[e]);
	}
	N=sc.SC.size();
	FOR(i,N) FORR(e,E[i]) in[e]++;
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		ma[x]+=num[x];
		FORR(e,E[x]) {
			ma[e]=max(ma[e],ma[x]);
			in[e]--;
			if(in[e]==0) Q.push(e);
		}
	}
	
	cout<<*max_element(ma,ma+N)<<endl;
	
	
}

まとめ

こういうのに永続(およびPersistent)という単語を使うのに若干の違和感を感じる。
いや、いい悪いとか正しい正しくないではなく、分野の違いによる単語の扱いの違いなんだけどね。
とはいえ更新が根に伝搬するあたりは親近感がある。