Problem 161 (C++で)

Project Euler

C++だと実行時間はどう変わるのか
同じアルゴリズムで実装してみた

#include <iostream>
#include <map>
using namespace std;
int h=12,w=9;
int area[][3]={{0,w,w+1},{0,w,w-1},{0,w+1,1},{0,w,1},{0,w,2*w},{0,1,2}};
bool inBoard(int x,int t){
  switch(t){
  case 1: return x/w<h-1 && x%w>0;
  case 4: return x/w<h-2;
  case 5: return x%w<w-2;
  default: return x/w<h-1 && x%w<w-1;
  }
}
bool canPut(bool board[],int x,int t){
  if(!inBoard(x,t))return false;
  for(int i=0;i<3;i++)if(board[x+area[t][i]])return false;
  return true;
}
long shape(bool board[]){
  long long s=0;
  for(int i=0,j,t,p;i<w;i++,s=2*h*s+t+p)
    for(p=0,t=0,j=0;j<h;j++)if(board[w*j+i]){
	p=t;
	t=j+1;
      }
  return s;
}
long long solve(map<long,long long> &memo,bool board[],int x){
  long s = shape(board);
  if(memo.find(s)!=memo.end()) return memo[s];
  if(x==h*w) return 1;
  if(board[x]) return solve(memo,board,x+1);
  long long count=0;
  for(int t=0;t<6;t++)
    if(canPut(board,x,t)){
      for(int i=0;i<3;i++)board[x+area[t][i]]=true;
      count+=solve(memo,board,x+1);
      for(int i=0;i<3;i++)board[x+area[t][i]]=false;
    }
  if(count>1) memo[s]=count;
  return count;
}
int main(){
  bool board[h*w];
  map<long,long long> memo;
  for(int i=0;i<h*w;i++)board[i]=false;
  cout << solve(memo,board,0) << "\n";
}

javaの約8割の時間だった。あんま速くないね。倍ぐらいになるかと思っていた。
どちらにしろ、おそらく、アルゴリズムというか実装というかが良くないと思われる。
大筋はＤＰで良いと思われるが、現在は効率が悪そう。
まぁ、解けたからいいや。
以下C++で手間取ったところ

[C++メモ]

次の配列宣言はダメ

int[] arr;

次の配列引数はダメ

void func(int[] arr){

正しくはこんな感じ

int arr[]
  • 関数の引数に配列を入れると勝手に参照渡し(ポインタ渡し？）になるが、他は値渡しになる

javaだと基本的に参照渡しなので、その感覚でやってたら、mapを渡すところでハマッタ。
mapが更新されねー、配列は更新されるのにー、とかなった。

[追記]

hash map を使わずにC++で

#include <iostream>
#define H 12
#define W 9
#define S 1953125
using namespace std;
int area[][3]={{0,W,W+1},{0,W,W-1},{0,W+1,1},{0,W,1},{0,W,2*W},{0,1,2}};
bool inBoard(int x,int t){
  switch(t){
  case 1: return x/W<H-1 && x%W>0;
  case 4: return x/W<H-2;
  case 5: return x%W<W-2;
  default: return x/W<H-1 && x%W<W-1;
  }
}
bool canPut(bool board[],int x,int t){
  if(!inBoard(x,t))return false;
  for(int i=0;i<3;i++)if(board[x+area[t][i]])return false;
  return true;
}
int shape(bool board[],int z){
  int s=0;
  for(int i=0,t=0;i<W;i++,s=5*s+t,t=0)
    for(int j=0;j<3&&(z+j)*W+i<H*W;j++)
      if(board[(z+j)*W+i])t+=j==1? 2: 1;
  return s;
}
long long solve(long long memo[][S],bool board[],int x){
  if(x==H*W) return 1;
  if(board[x]) return solve(memo,board,x+1);
  int z=x/W,s=shape(board,z);
  if(memo[z][s]>0) return memo[z][s];
  long long count=0;
  for(int t=0;t<6;t++)
    if(canPut(board,x,t)){
      for(int i=0;i<3;i++)board[x+area[t][i]]=true;
      count+=solve(memo,board,x+1);
      for(int i=0;i<3;i++)board[x+area[t][i]]=false;
    }
  memo[z][s]=count;
  return count;
}
int main(){
  bool board[H*W];
  long long (*memo)[S]=new long long[H][S];
  for(int i=0;i<H*W;i++)board[i]=false;
  for(int i=0;i<H;i++)for(int j=0;j<S;j++)memo[i][j]=-1;
  cout << solve(memo,board,0) << "\n";
  delete [] memo;
}

javaでは

import java.util.*;
public class P161_1{
    static long[][] memo;
    static boolean[] board;
    static int h=12,w=9;
    static long solve(int x){
	if(x==h*w)return 1;//finish 
	if(board[x])return solve(x+1);//filled
	int z = x/w,s=shape(z);
	if(memo[z][s]>0)return memo[z][s];
	long count=0;
	for(Triomino t:EnumSet.range(Triomino.NorthEast,Triomino.Horizon))//next step
	    if(canPut(x,t)){
		for(int y:t.area(w))board[x+y]=true;//put Triomino
		count+=solve(x+1);
		for(int y:t.area(w))board[x+y]=false;//remove Triomino
	    }
	memo[z][s]=count;
	return count;
    }
    static boolean canPut(int x,Triomino t){
	if(!t.canPut(h,w,x))return false;
	for(int y:t.area(w))if(board[x+y])return false;
	return true;
    }
    static int shape(int z){
	int s=0;
	for(int i=0,t=0;i<w;i++,s=5*s+t,t=0)
	    for(int j=0;j<3&&(z+j)*w+i<h*w;j++)
		if(board[(z+j)*w+i])t+=j==1? 2: 1;
	return s;
    }
    public static void main(String[] args){
	board=new boolean[h*w];
	memo = new long[h][(int)Math.pow(5,w)];
	for(int i=0;i<h;i++)Arrays.fill(memo[i],-1);
	System.out.println("result:"+solve(0));
    }
}
enum Triomino{
    NorthEast,NorthWest,SouthWest,SouthEast,Vertical,Horizon;
    public int[] area(int w){
	switch(this){
	case NorthEast: return new int[] {0,w,w+1};
	case NorthWest: return new int[] {0,w,w-1};
	case SouthWest: return new int[] {0,w+1,1};
	case SouthEast: return new int[] {0,w,1};
	case Vertical: return new int[] {0,w,2*w};
	case Horizon: return new int[] {0,1,2};
	default: return null;
	}
    }
    public boolean canPut(int h,int w,int x){
	switch(this){
	case NorthWest: return x/w<h-1 && x%w>0;
	case Vertical: return x/w<h-2;
	case Horizon: return x%w<w-2;
	default: return x/w<h-1 && x%w<w-1;
	}
    }
}