解いた問題のソースコードと解説など。


SRM 484 Div2 Hard CubeColoring

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11130&rd=14237

互いに区別できる立方体の頂点に色を塗りたい。良い塗りとは隣あう頂点が異なる色で、かつそれぞれの頂点にふさわしい色が塗られている時である。ふさわしい色はvector < string > colorsで与えられる。i番目の要素のj番目が'Y'であるとき頂点iに色jがふさわしいことを表す。'N'であるときはふさわしくないことを表す。良い塗りの総数を返せ。

やりかた

Editorialを参考にしました。

頂点0,2,5,7は互いに隣あわないのでふさわしい色ならどの色を塗っても良い。これらの各組み合わせに対し、(頂点1に塗れる色数) * (頂点3に塗れる色数) * (頂点4に塗れる色数) * (頂点6に塗れる色数)を計算し、和を取ればいい。

以下ソース。

class CubeColoring {
public:
  long long theCount(vector <string> colors) {
    long long result = 0;
    int L = colors[0].length();
    for(int c0 = 0; c0 < L; c0++) if(colors[0][c0] == 'Y') 
    for(int c2 = 0; c2 < L; c2++) if(colors[2][c2] == 'Y') 
    for(int c5 = 0; c5 < L; c5++) if(colors[5][c5] == 'Y') 
    for(int c7 = 0; c7 < L; c7++) if(colors[7][c7] == 'Y') {
	ll cnt1 = 0, cnt3 = 0, cnt4 = 0, cnt6 = 0;
	for(int c1 = 0; c1 < L; c1++) 
	  if(colors[1][c1] == 'Y' && c1 != c0 && c1 != c2 && c1 != c5) cnt1++;
	for(int c3 = 0; c3 < L; c3++) 
	  if(colors[3][c3] == 'Y' && c3 != c0 && c3 != c2 && c3 != c7) cnt3++;
	for(int c4 = 0; c4 < L; c4++) 
	  if(colors[4][c4] == 'Y' && c4 != c0 && c4 != c5 && c4 != c7) cnt4++;
	for(int c6 = 0; c6 < L; c6++) 
	  if(colors[6][c6] == 'Y' && c6 != c2 && c6 != c5 && c6 != c7) cnt6++;
	result += (cnt1 * cnt3 * cnt4 * cnt6);
      }
    return result;
  }
};

これはできてしかるべきだった。干渉しあわないところから塗っていくという考え方は覚えておきたい。

しょげないでよBaby 眠れば治る