kmjp's blog

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

TopCoder SRM 805 : Div1 Easy Div2 Hard ThreeDChessRooks

久々にレート大幅増。
https://community.topcoder.com/stat?c=problem_statement&pm=16943&rd=18678

問題

C*C*Cの3次元グリッド上で、N個のセルの位置が指定される。
以下を満たすセルのordered pairは何通りか。

  • 1つの指定セルに白いルークを置き、もう1つの指定セルに黒いルークを置く
  • 先手は、白いルークを黒いルークにぶつからないように動かすことができる
  • 後手は、黒いルークを白いルークにぶつかるように動かすことができる

解法

値としては
(X座標が一致する指定セルのペアの数)+(Y座標が一致する~~)+(Z座標が一致する~~)-(X座標とY座標が一致する~~)-(Y座標とZ座標が一致する~~)-(X座標とZ座標が一致する~~)-(先手の動きに制限がかかるケース)
となる。
全座標が一致するセルの対は数えなくてよい(上記ケースで、3回加算されて3回減算されるため)。

最後のコーナーケースだが、2つの座標が一致する指定セルで、残りの座標が(0,1)または(C-1,C-2)の場合、先手は一致している座標をずらす方向にしか動かせないので、取り除く必要がある。

ll Xs[1010101];
ll Ys[1010101];
ll Zs[1010101];
map<pair<int,int>,vector<int>> M[3];
class ThreeDChessRooks {
	public:
	long long count(int C, int R, vector <int> XP, vector <int> YP, vector <int> ZP, int seed) {
		vector<ll> X,Y,Z;
		int i;
		FOR(i,XP.size()) {
			X.push_back(XP[i]);
			Y.push_back(YP[i]);
			Z.push_back(ZP[i]);
		}
		ll s=seed;
		FOR(i,R-XP.size()) {
			s = (s * 1103515245 + 12345)%(1LL<<31);
			X.push_back(s%C);
			s = (s * 1103515245 + 12345)%(1LL<<31);
			Y.push_back(s%C);
			s = (s * 1103515245 + 12345)%(1LL<<31);
			Z.push_back(s%C);
		}
		ZERO(Xs);
		ZERO(Ys);
		ZERO(Zs);
		FOR(i,3) M[i].clear();
		
		ll ret=0;
		FOR(i,R) {
			Xs[X[i]]++;
			Ys[Y[i]]++;
			Zs[Z[i]]++;
			M[0][{Y[i],Z[i]}].push_back(X[i]);
			M[1][{X[i],Z[i]}].push_back(Y[i]);
			M[2][{X[i],Y[i]}].push_back(Z[i]);
		}
		FOR(i,C) {
			ret+=Xs[i]*(Xs[i]-1);
			ret+=Ys[i]*(Ys[i]-1);
			ret+=Zs[i]*(Zs[i]-1);
		}
		FOR(i,3) {
			FORR(m,M[i]) {
				auto v=m.second;
				ret-=v.size()*(v.size()-1);
				map<int,int> A;
				FORR(a,v) A[a]++;
				ret-=1LL*A[1]*A[0];
				ret-=1LL*A[C-1]*A[C-2];
			}
		}
		
		return ret;
	}
}

まとめ

無駄に神経を使う問題だった…。