久々にレート大幅増。
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; } }
まとめ
無駄に神経を使う問題だった…。