「オイラープロジェクト211～220」の編集履歴（バックアップ）一覧に戻る
*問い215
この問題は条件がきついので全探索でも行けるかもしれないと考えたのですが念のためメモ化計算でいってみました。
出てきた数字は&bold(){806844323190414}通りと意外と大きなものでしたが計算は一瞬で終わりました。
左端から全段完璧に仕上げていくという方法を取ることで下から積み上げるより計算量を減らせます。
解法は３分でおもいつきましたが、コードの記述にはめちゃ時間かかりました。
そのかいあってコードはめちゃ高速に動きます。
横から完璧に仕上げていけば計算量が減る。
仮の話ですが単純使い捨て労働者にこの組み合わせ数を求めるのが毎日の自分の仕事といえば、誰でもこの程度の工夫は普通に行うでしょう。
プログラムだと問題が抽象的になるぶんこの程度の素朴な発想でも気付かないときは気付かないものですが。
縦のものを横に、たったこれだけのことです。
#include<stdio.h>
#include<map>
#include<string.h>
#include<iostream>
const int h=10;
const int w=32;
struct S{
int cols[3][h+2];//左端から全段煉瓦を積み上げる上段下段に番兵を置く
int rights[h+2];//今積んでいる位置から右端何個目まで到達しているか
bool operator<(const S& s)const{
for(int i=1;i<=h;i++){
if(cols[0][i]!=s.cols[0][i])return cols[0][i]<s.cols[0][i];
if(cols[1][i]!=s.cols[1][i])return cols[1][i]<s.cols[1][i];
}
return false;
}
void rShiftCopy(S& s){
memcpy(s.cols[0],cols[1],sizeof(cols[1]));
memcpy(s.cols[1],cols[2],sizeof(cols[2]));
memset(s.cols[2],0,sizeof(s.cols[2]));
s.rights[0]=s.rights[h+1]=0;//上段下段の番兵
for(int i=1;i<=h;i++){
s.rights[i]=rights[i]-(rights[i]>0);//0以上なら引く
}
}
};
std::map<S,__int64> memo,next;
S nextS;
void saiki(S& s,int deep,int col,__int64 p){
if(deep<=h){
if(s.cols[0][deep]==1){
saiki(s,deep+1,col,p);
}else{
if(col+2>w)return ;//右端をはみ出した
if(s.rights[deep-1]!=2&&s.rights[deep+1]!=2){
if(col+2==w)s.rights[deep]=-10;//端に到達
else s.rights[deep]=2;//２つブロック
//上段に２ブロックがないかチェック
s.cols[0][deep]=s.cols[1][deep]=1;
s.cols[2][deep]=0;//あり得ないが念のため
saiki(s,deep+1,col,p);//２つブロックで次へ
s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=0;
s.rights[deep]=0;
}
if(col+3>w)return ;//右端をはみ出した
if(s.rights[deep-1]!=3&&s.rights[deep+1]!=3){
if(deep<h-1&&s.rights[deep+1]==3)return ;//上段に３ブロックが
if(col+3==w) s.rights[deep]=-10;//端に到達
else s.rights[deep]=3;//３つブロック
s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=1;
saiki(s,deep+1,col,p);
s.cols[0][deep]=s.cols[1][deep]=s.cols[2][deep]=0;
s.rights[deep]=0;
}
}
}else{
s.rShiftCopy(nextS);
if(next.find(nextS)==next.end()){
next[nextS]=p;
}else{
next[nextS]+=p;
}
}
}
int main(){
std::map<S,__int64>::iterator it;
S s,last,s2;
__int64 p;
memset(s.cols,0,sizeof(s.cols));
memset(s.rights,0,sizeof(s.rights));
last=s;//最後の集計用
for(int i=1;i<=h;i++)last.cols[0][i]=1;
memo[s]=1;
for(int i=0;i<w-1;i++){
for(it=memo.begin();it!=memo.end();it++){
s=(*it).first;
p=(*it).second;
saiki(s,1,i,p);
}
memo.clear();//ここは計算量より分かりやすさです。
memo.insert(next.begin(),next.end());
next.clear();
}
std::cout<<memo[last];
}
