Codeforces #346 Div2. F. Polycarp and Hay

なんか変な問題。
http://codeforces.com/contest/659/problem/F

問題

2次元グリッドの各セルに整数A[r][c]が書かれている。
各セルの整数は任意回数デクリメント可能な時、以下のような状態にすることは可能か。
可能なら例を示せ。

• 全セルの数値の和はKである。
• 全てのA[r][c]は0であるかある等しい正整数のいずれかである。
• A[r][c]が非0のセルのうち、1つはデクリメントを1度もしていないセルがある。
• A[r][c]が非0のセル群はすべて連結である。

解法

A[r][c]の大きな順に、セル(r,c)に対し非0のセルの値がすべてA[r][c]となるようにデクリメントした際条件を満たせるか判定する。
それには各セル(r,c)に対し以下の処理を行う。

• 上下左右の隣接マスに対し、A[r][c]以上の値のセルがあればUnion-Findで連結する。
• KがA[r][c]で割りきれ、かつ(r,c)の連結セル数がK/A[r][c]以上なら題意を満たす状態が構築可能である。
  • その場合、(r,c)からDFSの要領でK/A[r][c]個の連結セルだけ値をA[r][c]にし、それ以外は0にする。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	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 i; FOR(i,um) 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;
	}
};

int H,W;
ll K;
int A[1010][1010];
UF<1010101> uf;

void dfs(int y,int x,int v) {
	int i;
	if(K<=0) return;
	K--;
	A[y][x]=v;
	
	FOR(i,4) {
		int dd[4]={1,0,-1,0};
		int ty=y+dd[i];
		int tx=x+dd[i^1];
		if(tx<0 || tx>=W || ty<0|| ty>=H) continue;
		if(A[ty][tx]) continue;
		if(uf[ty*1000+tx]!=uf[y*1000+x]) continue;
		if(K<=0) return;
		dfs(ty,tx,v);
		if(K<=0) return;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	
	vector<pair<int,int>> V;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		V.push_back({-A[y][x],y*1000+x});
	}
	sort(ALL(V));
	FORR(r,V) {
		y=r.second/1000;
		x=r.second%1000;
		int id=y*1000+x;
		
		if(y&&A[y-1][x]>=A[y][x]) uf(id-1000,id);
		if(y<H-1&&A[y+1][x]>=A[y][x]) uf(id+1000,id);
		if(x&&A[y][x-1]>=A[y][x]) uf(id-1,id);
		if(x<W-1&&A[y][x+1]>=A[y][x]) uf(id+1,id);
		
		if(K%A[y][x]==0 && (ll)A[y][x]*uf.count(id)>=K) {
			i=A[y][x];
			ZERO(A);
			K/=i;
			dfs(y,x,i);
			_P("YES\n");
			FOR(y,H) FOR(x,W) _P("%d%s",A[y][x],(x==W-1)?"\n":" ");
			return;
		}
	}
	_P("NO\n");
	
}

まとめ

まぁFと言っても2000ptなのでやさしめかな。