Codeforces LATOKEN Round 1 : F2. Falling Sand (Hard Version)

またややこしい問題設定。
https://codeforces.com/contest/1534/problem/F2

問題

N*Mのグリッドがあり、一部のマスは砂のブロックとなっている。
ここで、いくつかのブロックを指定すると、その砂は形を保ったまま落下する。
その際、途中隣接セルに他のブロックがあれば、それらも連鎖的に落下するものとする。

各列に対し、最低何個以上のブロックを落下させたいという条件が与えられる。
それらの条件を満たすには、最低何個のブロックを最初指定する必要があるか。

解法

このブロックを落下させると、このブロックも落下する、という関係を有向グラフで表現しよう。
そしてこのグラフを強連結成分分解して縮約すると、入次数0の点が指定対象となる。

この時、各点を落下させることで、どの列からどの列の落下数条件を満たすことができるか、区間で表現される。
あとは、区間スケジューリング問題の要領で、できるだけ少ない区間の数で全列をカバーしよう。

int H,W;
string S[404040];
int A[404040];

class SCC {
public:
	static const int MV = 2025000;
	vector<vector<int> > SC; int NV,GR[MV];
	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;
int vis[404040];

vector<int> E[404040];
int in[404040];
int LL[404040],RR[404040];
int nd[404040];
int reachable[404040];
int need[404040];
vector<int> Rs[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[H-1-y];
	FOR(x,W) {
		cin>>A[x];
		if(A[x]>0) {
			nd[x]=1;
			FOR(y,H) if(S[y][x]=='#') {
				A[x]--;
				if(A[x]==0) need[y*W+x]=1;
			}
		}
	}
	
	scc.init(H*W);
	FOR(x,W) {
		int pre=-2;
		FOR(y,H) if(S[y][x]=='#') {
			if(pre>=0) scc.add_edge(y*W+x,pre*W+x);
			if(pre+1==y) scc.add_edge(pre*W+x,y*W+x);
			pre=y;
		}
	}
	FOR(x,W-1) {
		int py1=-2,py2=-2;
		FOR(y,H) {
			if(S[y][x]=='#') py1=y;
			if(S[y][x+1]=='#') py2=y;
			if(S[y][x]=='#'&&py2>=0) scc.add_edge(y*W+x,py2*W+x+1);
			if(S[y][x+1]=='#'&&py1>=0) scc.add_edge(y*W+x+1,py1*W+x);
		}
	}
	scc.scc();
	
	FOR(i,scc.SC.size()) {
		LL[i]=401040;
		RR[i]=-1;
		x=0;
		FORR(v,scc.SC[i]) {
			if(S[v/W][v%W]=='#') vis[i]++;
		}
		if(vis[i]==0) continue;
		if(reachable[i]) {
			FORR(v,scc.SC[i]) if(need[v]) nd[v%W]=need[v]=0;
		}
		FORR(v,scc.SC[i]) {
			if(S[v/W][v%W]=='#') vis[i]++;
			if(need[v]) {
				LL[i]=min(v%W,LL[i]);
				RR[i]=max(v%W,RR[i]);
				reachable[i]=1;
			}
		}
		FORR(v,scc.SC[i]) {
			FORR(e,scc.E[v]) if(scc.GR[e]!=scc.GR[v]) {
				reachable[scc.GR[e]]|=reachable[i];
				in[i]++;
				E[scc.GR[e]].push_back(i);
			}
		}
	}
	queue<int> Q;
	FOR(i,scc.SC.size()) if(vis[i]&&in[i]==0) Q.push(i);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		FORR(e,E[x]) {
			LL[e]=min(LL[e],LL[x]);
			RR[e]=max(RR[e],RR[x]);
			
			in[e]--;
			if(in[e]==0) Q.push(e);
		}
		Rs[LL[x]].push_back(RR[x]);
	}
	
	int ret=0;
	int ma=-1;
	FOR(x,W) {
		FORR(r,Rs[x]) ma=max(ma,r);
		if(nd[x]) {
			ret++;
			for(i=x;i<=ma;i++) nd[i]=0;
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

やりたいことはともかく、コード量が割かし多い。