「オイラープロジェクト161～170」の編集履歴（バックアップ）一覧はこちら
オイラープロジェクト161～170 - (2012/09/02 (日) 11:18:01) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い161
とりあえず速さより分かりやすさを重視して一段ずつ動的計画法というかメモ化というかそんな感じ。
途中までは３段ずつみていき、最後の段を超えてピースをはめ込めないように注意すればそんなに難しくはない。
うーんとりあえず素朴に求めたけどもっと賢い方法が幾らでもありそう？
#include<stdio.h>
#include<string.h>
#include<map>
#include<iostream>
const int w=9;
const int h=12;
struct S{
int row[3][w];
bool operator<(const S& s)const{
for(int c=0;c<w;c++){
if(row[0][c]!=s.row[0][c])return row[0][c]<s.row[0][c];
if(row[1][c]!=s.row[1][c])return row[1][c]<s.row[1][c];
}
return false;
}
};
std::map<S,__int64> memo,next;
int pxs[][2]={ {0,1},
{1,1},
{0,1},
{0,-1},
{0,0},
{1,2}};
int pys[][2]={ {1,0},
{0,1},
{1,1},
{1,1},
{1,2},
{0,0}};
void saiki(S& s,int deep,__int64 perm,int row){
if(deep==w){
S nextS;
memset(nextS.row,0,sizeof(nextS.row));
memcpy(nextS.row[0],s.row[1],sizeof(s.row[1]));
memcpy(nextS.row[1],s.row[2],sizeof(s.row[2]));
if(next.find(nextS)==next.end()){
next[nextS]=perm;
}else{
next[nextS]+=perm;
}
}else{
if(s.row[0][deep]!=0){
saiki(s,deep+1,perm,row);
}else{
int px1,px2,py1,py2;
for(int i=0;i<6;i++){
px1=deep+pxs[i][0];
px2=deep+pxs[i][1];
py1=pys[i][0];
py2=pys[i][1];
if(px1<0||w<=px1||px2<0||w<=px2)continue;
if(py1<0||h<=py1+row||py2<0||h<=py2+row)continue;
if(s.row[py1][px1]!=0||s.row[py2][px2]!=0)continue;
s.row[py1][px1]=s.row[py2][px2]=1;
saiki(s,deep+1,perm,row);
s.row[py1][px1]=s.row[py2][px2]=0;
}
}
}
}
int main(){
std::map<S,__int64>::iterator it;
S s,ansS;
__int64 ans=0;
memset(ansS.row,0,sizeof(ansS.row));
memset(s.row,0,sizeof(s.row));
memo[s]=1;
for(int r=0;r<h;r++){
for(it=memo.begin();it!=memo.end();it++){
s=(*it).first;
saiki(s,0,(*it).second,r);
}
memo.clear();
memo.insert(next.begin(),next.end());
next.clear();
//if(r>=h-3){
//ans+=memo[ansS];
//std::cout<<ans<<" ";
// if(r==h-3)memset(ansS.row[1],0,sizeof(ansS.row[1]));
// if(r==h-2)memset(ansS.row[0],0,sizeof(ansS.row[0]));
//}
}
std::cout<<memo[ansS];
}
*問い161
http://projecteuler.net/problem=161
とりあえず速さより分かりやすさを重視して一段ずつ動的計画法というかメモ化というかそんな感じ。
途中までは３段ずつ注目し、最後の２段は最後の段を超えてピースをはめ込めないように注意すればそんなに難しくはない。
うーんとりあえず素朴に求めたけどもっと賢い方法が幾らでもありそう？
問題が１２０番を超えたあたりから素朴な方法では解けず整数論の知識がいる問題が増えてきたようである。
そんな中こういう素朴に解ける問題を見つけると砂漠の中でオアシスを見つけたような気分になる。
#include<stdio.h>
#include<string.h>
#include<map>
#include<iostream>
const int w=9;
const int h=12;
struct S{
int row[3][w];
bool operator<(const S& s)const{
for(int c=0;c<w;c++){
if(row[0][c]!=s.row[0][c])return row[0][c]<s.row[0][c];
if(row[1][c]!=s.row[1][c])return row[1][c]<s.row[1][c];
}
return false;
}
};
std::map<S,__int64> memo,next;
int pxs[][2]={ {0,1},
{1,1},
{0,1},
{0,-1},
{0,0},
{1,2}};
int pys[][2]={ {1,0},
{0,1},
{1,1},
{1,1},
{1,2},
{0,0}};
void saiki(S& s,int deep,__int64 perm,int row){
if(deep==w){
S nextS;
memset(nextS.row,0,sizeof(nextS.row));
memcpy(nextS.row[0],s.row[1],sizeof(s.row[1]));
memcpy(nextS.row[1],s.row[2],sizeof(s.row[2]));
if(next.find(nextS)==next.end()){
next[nextS]=perm;
}else{
next[nextS]+=perm;
}
}else{
if(s.row[0][deep]!=0){
saiki(s,deep+1,perm,row);
}else{
int px1,px2,py1,py2;
for(int i=0;i<6;i++){
px1=deep+pxs[i][0];
px2=deep+pxs[i][1];
py1=pys[i][0];
py2=pys[i][1];
if(px1<0||w<=px1||px2<0||w<=px2)continue;
if(py1<0||h<=py1+row||py2<0||h<=py2+row)continue;
if(s.row[py1][px1]!=0||s.row[py2][px2]!=0)continue;
s.row[py1][px1]=s.row[py2][px2]=1;
saiki(s,deep+1,perm,row);
s.row[py1][px1]=s.row[py2][px2]=0;
}
}
}
}
int main(){
std::map<S,__int64>::iterator it;
S s,ansS;
__int64 ans=0;
memset(ansS.row,0,sizeof(ansS.row));
memset(s.row,0,sizeof(s.row));
memo[s]=1;
for(int r=0;r<h;r++){
for(it=memo.begin();it!=memo.end();it++){
s=(*it).first;
saiki(s,0,(*it).second,r);
}
memo.clear();
memo.insert(next.begin(),next.end());
next.clear();
//if(r>=h-3){
//ans+=memo[ansS];
//std::cout<<ans<<" ";
// if(r==h-3)memset(ansS.row[1],0,sizeof(ansS.row[1]));
// if(r==h-2)memset(ansS.row[0],0,sizeof(ansS.row[0]));
//}
}
std::cout<<memo[ansS];
}
