UnKoder #08 : C. Rainbow Hex

ちょっと悩む問題。
https://www.hackerrank.com/contests/unkoder-08/challenges/rainbow-hex

問題

Hex Gridを7色で塗り分けたい。
この際、どの1マスとその周囲６マスを見ても、その７マスは異なる7色であるようにしたい。

ここでN箇所のマス(X[i],Y[i])の色が指定されている。
条件を満たす塗り分け方は何通りあるか。

解法

原点とその周囲６マスの色を固定させたとする。
その場合、他のマスの色の塗り分け方は２通りある。
すなわち(x,y)と(x+1,y+2)の色が一致するパターンと、(x,y)と(x+1,y-3)の色が一致するパターンである。

これらを用いて(X[i],Y[i])の色から、原点とその周囲６マスの色を確定させていく。
同じマスに２色割当たるケースや、逆に１色が２マスに割当たってはならない。
未割当の色・マスがP個あれば、P!がその塗り分け方における色の割り当てとなる。

塗り分け方は２通りなので、上記処理を行うと良い。

(上記では「原点とその周囲６マスの色を確定させていく」と書いたが、以下のコードでは計算を単純にするため(0,0)～(0,6)の６マスに置き換えている。)

int N;
ll X[51],Y[51];
int C[51];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i]>>C[i];
	
	int ret=0;
	FOR(x,2) {
		set<int> S[7];
		FOR(i,N) {
			ll yy=Y[i] + ((x==0)?(-2):3)*X[i];
			S[(yy%7+7)%7].insert(C[i]);
		}
		
		int ng=0;
		FOR(i,7) {
			if(S[i].size()>1) ng++;
			int num=0;
			FOR(j,7) num+=S[j].count(i+1);
			if(num>1) ng++;
		}
		if(ng) continue;
		
		int num=0;
		FOR(i,7) num += S[i].size()==0;
		int pat=1;
		FOR(i,num) pat*=(i+1);
		ret+=pat;
	}
	cout<<ret<<endl;
}

まとめ

面白い問題でした。
色鉛筆は使わなかったけど。