AtCoder AGC #017 : E - Jigsaw

Dよりこっちの方が解けてたかも。
http://agc017.contest.atcoder.jp/tasks/agc017_e

問題

以下の形状のピースがN個与えられる。

• 各ピースは、幅1高さが整数の長方形を横に3つつなげた形状をしている。
• 真ん中のパーツは高さH固定である。
• 左側のパーツは高さA[i]で、下辺は真ん中のパーツの下辺よりC[i]だけ高い位置にある。
• 右側のパーツは高さB[i]で、下辺は真ん中のパーツの下辺よりD[i]だけ高い位置にある。

N個のピースを横につなげていくことを考える。
この時、以下の条件を満たすようにつなげたい。

• 真ん中のパーツが置かれる高さはすべて同じ。
• 左右のパーツは、下辺が真ん中のパーツの下辺と同じ高さであるか、隣のピースのパーツの上辺の高さに等しい。

条件を満たすピースのつなぎ方は存在するか判定せよ。

解法

各ピースは、左右パーツについて下辺が真ん中のパーツの下辺より浮いているか浮いていないかで大雑把に分類できる。
パーツを左から順に右に並べていくことを考えると、以下の条件を満たさなければならない。

• 最も左におくピースは、左パーツが浮いていてはならない。
• 右パーツが浮いている場合、その右には左パーツが浮いていないピースがなければならない。
• 最も右におくピースは、右パーツが浮いていてはならない。

右パーツがRだけ浮いている(+R)、または右パーツが浮いておらずその高さがRである(-R)という状態を頂点とするグラフを考える。
そうすると、各ピースは頂点間を連結する辺として表現できる。
また、初期状態に相当する頂点をVとすると、Vから+Rの頂点には任意に辺を追加可能だし、-Rの頂点からVには任意に辺を追加可能である。

さて、全ピースを1回ずつ使うということは全辺を1回ずつたどるということになる。
そのためには全辺が連結かつ入次数と出次数が一致すればよい。
まず入次数と出次数が不一致の頂点については、辺の追加で対応可能なら追加しよう。
あとはこれらの辺をUnion-Findで連結し、単一連結成分になるか判定すればよい。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<2000> uf;

int in[2000];
int out[2000];

int N,H;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H;
	FOR(i,N) {
		int A,B,C,D,L,R;
		cin>>A>>B>>C>>D;
		if(C>0) L=C;
		else L=-A;
		if(D==0) R=B;
		else R=-D;
		
		out[L+1000]++;
		in[R+1000]++;
		uf(L+1000,R+1000);
	}
	
	for(i=-200;i<=-1;i++) {
		if(in[i+1000]>out[i+1000]) return _P("NO\n");
		if(in[i+1000]<out[i+1000]) uf(1000,i+1000);
	}
	for(i=1;i<=200;i++) {
		if(in[i+1000]<out[i+1000]) return _P("NO\n");
		if(in[i+1000]>out[i+1000]) uf(1000,i+1000);
	}
	
	for(i=1000-200;i<=1000+200;i++) if((in[i]||out[i]) && uf[i]!=uf[1000]) return _P("NO\n");
	_P("YES\n");
}

まとめ

考察は若干重いが実装は軽め。