DouKaku? 4835 minke: $ g++ -O3 maho.cpp &...(魔方分割数)

Comment detail

$ 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;
}

ビットの集合を生成後、ソートするようにしたら17秒ぐらいになりました:p

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;
}

#4835ほぼそのまま移植(違いは進捗をprintするぐらい)ですが、こんなになりましたorz。

2316.28 real 2312.21 user 1.48 sys

もう少し工夫しないとだめですね、こりゃ。

Dan the Perl Monger

#!/usr/local/bin/perl
use strict;
use warnings;

my @bits;
my $n  = shift || 3;
my $n2 = $n * $n;
my $cnt = 0;

sub comb {
    my ($a, $k, $s, $b) = @_;
    if ($k < $n-1){
        comb($_+1, $k+1, $s-$_, $b|1<<($_+1)) for ($a .. $n2-1);
    }else{
        push @bits, $b|1<<($s+1) if $a <= $s && $s <= $n2;
    }
}

sub calc{
    my ($s, $k, $b) = @_;
    if ($k == $n){
        printf "%d\r", $cnt++;
        return;
    }
    for my $i ($s..@bits-1){
        next if $b & $bits[$i];
        calc($i, $k+1, ($b | $bits[$i]));
    }
}

comb(1, 0, ($n * ($n2+1) / 2), 0);
@bits = sort {$a <=> $b} @bits;
calc(0, 0, 0);
print "$cnt\n";

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq