魔方分割数 in C++ DouKaku?

1 .. N^2までの数をN個の数字の和が等しいN個のグループに分けたいと思います。

たとえば、N=3のときは、
(1) { 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }
(2) { 1, 6, 8 }, { 2, 4, 9 }, { 3, 5, 7 }
の2通りの方法があります。

ここで指定されたNに対して、何通りのグループ分けの方法があるかを数えるプログラムを作ってください。
(何通りかという値だけが出力されればよいのですが、予め計算してある結果を返すのはダメですよ。)
また、N=5を指定したときの実行時間もあわせて教えてください。

なお、数え上げるときの注意として、

・{ 1, 5, 9 } と { 1, 9, 5 }は同じもの

・{ 1, 5, 9 }, { 2, 6, 7 }, { 3, 4, 8 }と
　{ 1, 5, 9 }, { 3, 4, 8 }, { 2, 6, 7 }は同じもの
とすることに注意してください。

$ g++ -O3 maho.cpp && time ./a.out
3245664

real    0m26.930s
user    0m22.310s
sys     0m4.560s

最初に和が (総和/n) となるn個の値の組を
ビット列として全パターン生成してしまいます。
そうしておいて、ビットパターンの中から排他的なものを選んでいくアルゴリズム。

それなりに速いかと。

#include <iostream>
#include <vector>
typedef unsigned int bit_t;

std::vector<bit_t> bits;
int n, n2, cnt = 0;

void comb(int a, int k, int s, bit_t b) {
  if (k < n-1)
    for (int i = a; i < n2; ++i)
      comb(i+1, k+1, s-i, b | 1 << (i-1));
  else
    if (a <= s && s <= n2)
      bits.push_back(b | 1 << (s-1));
}

void calc(int s, int k, bit_t b) {
  if (k == n) { ++cnt; return; }

  for (int i = s; i < (int)bits.size(); ++i)
    if (!(b & bits[i]))
      calc(i+1, k+1, b | bits[i]);
}

int main() {
  n = 5;
  n2 = n * n;
  int m = n * (n2+1) / 2;

  comb(1, 0, m, 0);
  calc(0, 0, 0);

  std::cout << cnt << std::endl;
}

n-1個の組を見つけた後、最後の一つを二分探索するようにしたら n=5 で5秒ぐらいになりました。
real    0m4.920s
user    0m2.920s
sys     0m1.980s

n=6 もやろうとしてみたのですが、32ビットでは全然足りなくて、
64ビットに収まるかどうかも怪しい感じですので、
解を1つずつカウントする方針では根本的に駄目そうです。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned int bit_t;

vector<bit_t> bits;
bit_t mask;
int n, n2;
long long cnt = 0LL;

void comb(int a, int k, bit_t b, int rest) {
  if (k == n-1) {
    if (rest <= n2)
      bits.push_back(b | 1 << (rest-1));
    return;
  }
  for (int i = a; i < n2; ++i)
    if (rest-i > i)
      comb(i+1, k+1, (b | 1 << (i-1)), rest-i);
}

void calc(int a, int k, bit_t b) {
  if (k == n-1) {
    if (binary_search(bits.begin()+a, bits.end(), mask & ~b))
      ++cnt;
    return;
  }
  for (int i = a; i < (int)bits.size(); ++i)
    if (!(b & bits[i]))
      calc(i+1, k+1, b | bits[i]);
}

int main(int argc, char **argv) {
  n = argc > 1 ? atoi(argv[1]) : 5;
  n2 = n * n;
  mask = (1 << n2) - 1;
  int m = n * (n2+1) / 2;

  comb(1, 0, 0, m);
  sort(bits.begin(), bits.end());
  calc(0, 0, 0);

  cout << cnt << endl;
}

DouKaku?

魔方分割数

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq