Codeforces #295 Div1 B. Cubes

なかなか面白い問題。
http://codeforces.com/contest/521/problem/B

問題

0～(M-1)の番号をふられたM個の正方形がある。
このM個の正方形はそれぞれ１辺の長さが1であり、２次元座標上に配置されている。
X軸が地面に相当するとして、各正方形はその上に(頂点が格子点に来るように)配置されている。

正方形の左下の点を(x,y)とする。
正方形が安定しておかれるには、以下の条件のいずれかを満たさなければならない。

• 正方形が地面の上に直接置かれる。すなわちy==0である。
• 正方形の下、辺または角を共有する位置に１個以上他の正方形がある。すなわち(x-1,y-1),(x,y-1),(x+1,y-1)を左下の点とする正方形が１個以上ある。

ここで２人でM個の正方形を交互に取り除くゲームを行う。
正方形を取り除く際は、正方形が不安定にならないようなものを取り除かなければならない。
取り除いた正方形は、順に前に取り除いた正方形の右に置いていく。

取り除いたM個の正方形の番号列をM桁のM進数の数値と考えたとき、先手は数を最大化、後手は数を最小化したい。
両者が最適手を取ったとき、最終的なM進数の数値はいくつになるか。

解法

M進数の数値は上の桁から順に決まることになる。
下の桁の影響は上の桁より小さいため、両者とも後の手の事は考えず、貪欲に取り除ける正方形のうち番号が最大・最小のものを取り除く。

よって、取り除ける正方形の番号をsetで管理すれば、単に最大値・最小値を交互に取り除いていけば良い。
あとは取り除ける番号のsetをどう管理するかである。

条件より、正方形を取り除けるのは、上((x-1,y+1)～(x+1,y+1)の3箇所)に他の正方形がある場合、それら上の正方形はいずれも下を支える正方形がいずれも２個以上ある場合に限る。
この条件をもとに取り除ける正方形を管理すればよい。

今回の問題で特徴的なのは、いったん取り除けると判定したのに再度取り除けなくなるパターンがあることである。
例えば左隣と真上に１個ずつ正方形がある場合、真上の正方形は左隣の正方形が支えるのでこの正方形は取り除くことができる。
ただし先に左隣を取り除かれると、正方形は取り除けなくなる(真上が先に取り除かれるのを待たなくてはならない)。

int M;
int X[101000],Y[101000];
map<pair<int,int>,int> P;
ll pm[101000];
set<int> up[101000],down[101000];
set<int> S;
ll mo=1000000009;

bool okok(int x) {
	bool ok=true;
	ITR(it,up[x]) ok &= down[*it].size()>=2;
	return ok;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	pm[0]=1;
	FOR(i,M) {
		pm[i+1]=pm[i]*M%mo;
		cin>>X[i]>>Y[i];
		P[make_pair(X[i],Y[i])]=i;
	}
	FOR(i,M) {
		for(j=-1;j<=1;j++) if(P.count(make_pair(X[i]+j,Y[i]+1))) {
			up[i].insert(P[make_pair(X[i]+j,Y[i]+1)]);
			down[P[make_pair(X[i]+j,Y[i]+1)]].insert(i);
		}
	}
	
	FOR(i,M) if(okok(i)) S.insert(i);
	ll ret=0;
	FOR(i,M) {
		if(i%2) x=*S.begin();
		else x=*S.rbegin();
		S.erase(x);
		ret += x*pm[M-1-i]%mo;
		
		ITR(it,up[x]) {
			y=*it;
			down[y].erase(x);
			if(okok(y)) S.insert(y);
			else S.erase(y);
			ITR(it2,down[y]) {
				if(okok(*it2)) S.insert(*it2);
				else S.erase(*it2);
			}
		}
		ITR(it,down[x]) {
			y=*it;
			up[y].erase(x);
			if(okok(y)) S.insert(y);
			else S.erase(y);
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

１回取り除けると判定されたのに、また取り除けないと判定が戻るケースがあるのが面白い。