ちょっと悩む問題。
https://www.hackerrank.com/contests/unkoder-08/challenges/rainbow-hex
問題
Hex Gridを7色で塗り分けたい。
この際、どの1マスとその周囲6マスを見ても、その7マスは異なる7色であるようにしたい。
ここでN箇所のマス(X[i],Y[i])の色が指定されている。
条件を満たす塗り分け方は何通りあるか。
解法
原点とその周囲6マスの色を固定させたとする。
その場合、他のマスの色の塗り分け方は2通りある。
すなわち(x,y)と(x+1,y+2)の色が一致するパターンと、(x,y)と(x+1,y-3)の色が一致するパターンである。
これらを用いて(X[i],Y[i])の色から、原点とその周囲6マスの色を確定させていく。
同じマスに2色割当たるケースや、逆に1色が2マスに割当たってはならない。
未割当の色・マスがP個あれば、P!がその塗り分け方における色の割り当てとなる。
塗り分け方は2通りなので、上記処理を行うと良い。
(上記では「原点とその周囲6マスの色を確定させていく」と書いたが、以下のコードでは計算を単純にするため(0,0)~(0,6)の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; }
まとめ
面白い問題でした。
色鉛筆は使わなかったけど。