SRM 457 Div2 Hard TheHexagonsDivTwo

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10694&rd=14144

正数n, kが与えられる。正六角形×6のハニカムのマス目に1～nまでの数字を埋めていく。隣り合うセルの数字a, bがa % k != b % kとなるように全てのセルに数字を埋める方法は何通りか。

やりかた

数 % k が隣り合わないように埋めていけばいい。1～nをmod kして、外郭から深さ優先探索。円順列なので最後に円周のセル数の6で割るのを忘れない。

以下ソース。

class TheHexagonsDivTwo {
public:
  map<int, int> rem;
  
  ll dfs(map<int, int> r, vector<int> col, int c){
    //ハニカムの真ん中を塗る時
    if(c == 6){
      map<int, int>::iterator it = r.begin();   
      //外郭の数字とすべて異なるような数字の数
      ll cnt = 0;
      for(; it != r.end(); it++){
	bool uni = true;
	for(int i = 0; i < 6; i++){
	  if(it -> first == col[i]) uni = false;
	}
	if(uni) cnt += it -> second;
      }
      return cnt;
    }
    
    //ハニカムの外郭を塗る時
    ll ret = 0; 
    map<int, int>::iterator it = r.begin();      
    for(; it != r.end(); it++){
      //隣り合う数字が違うことを確認
      if(it -> first != col[c - 1] && it -> first != col[(c + 1) % 6] && it -> second > 0){
	it -> second--;
	col[c] = it -> first;
	ret += (it -> second + 1) * dfs(r, col, c + 1);
	  it -> second++;
      }
    }
    return ret;
  }

  long long count(int n, int k) {
    rem.clear();
    //mod kとなる数字はいくつある?
    for(int i = 1; i <= n; i++)
      rem[i % k]++;

    vector<int> col(7, 1 << 29);
    return dfs(rem, col, 0) / 6;
  }

Div2 Hardを初めて自力で解けた。一発AC。（＾ω＾）　　∩（＾ω＾）∩わーい

今後はなるべくソースコメントを英語で書くようにします。