Problem 161 (C++で)
31 / Dec 2008C++だと実行時間はどう変わるのか
同じアルゴリズムで実装してみた
#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;
}
}
}