プロジェクトオイラー Problem 253 「お片づけ」 †

Problem 253 「お片づけ」 †

小さい子供が"数字イモムシ"を持っている. これは 40 のジグソーピースからなり, それぞれのピースは 1 つ数字が書いてあり, 一列につなげると 1 から 40 まで順番に並ぶ.

毎夜, 子供の父親は遊戯室にばらまかれたイモムシのピースを拾い集めなければならない. 父親は無作為にピースを拾っていき, 正しい順序に並べていく.
このようにイモムシを組み立てていくと, 徐々にくっついていっていくつかの断片が出来上がっていく.
断片の数は0(何もない状態)から始まり, だいたい 11 か 12 まで増えた後, やがてまた減っていき 1 (全部くっついた状態)で終わる.

例えば,

置かれたピース	現時点の断片
12	1
4	2
29	3
6	4
34	5
5	4
35	4
...	...

M を無作為にイモムシを片づける過程で起こった最大の断片の数とする.
10 ピースのイモムシの場合では, 各 M が起こる場合の数は

M	場合の数
1	512
2	250912
3	1815264
4	1418112
5	144000

つまり M の最頻値は 3 で平均値は 385643/113400 = 3.400732 である(小数点以下6桁に四捨五入).

40 ピースのイモムシの場合は M の最頻値は 11 である. では M の平均値は?

小数点以下6桁に四捨五入し回答せよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20253

解法
逆回しで40個そろった状態から一つずつ減らして分割していくと考えます。
lens[i]で長さiの断片がni個あると考えそこから減らしていきます。
１個の断片は断片が1個減ります。
2個の断片は左右どちらかが減ります。
3個以上の断片は左右どちらかが減るか二つの断片に分かれるかだけです。

減らすときできた組み合わせは残ってる全ピース数の多いほうから減らす形で計算します。

コード実行時間
3.08秒
平凡です。
もうちょっと早いコードを考えたいですね。

実はこのコード優先順位付きキューpqはいらずstd::setのaddS;もいりません。
全部std::mapのmemoだけで計算はできますが、わかりやすさを優先しました。



コード製作者　堀江伸一
兵庫県加古川市加古川町南備後



#include<stdio.h>
#include<iostream>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include <iomanip>
#include<time.h>

const int LIMIT=40;

struct S{
     //lens[1]は長さ１の断片がｎ1個ある
     //lens[2]は長さ２の断片がｎ2個ある
     int lens[LIMIT+1];
     int sum,split,splitMax;
   
     bool operator<(const S& s)const{
          if(sum!=s.sum)return sum<s.sum;
          if(split!=s.split)return split<s.split;
          if(splitMax!=s.splitMax)return splitMax<s.splitMax;
          for(int i=1;i<=LIMIT;i++){
               if(lens[i]!=s.lens[i])return lens[i]<s.lens[i];
          }
          return false;
     }
     void print(){
          printf("\n((inS sum=%d s=%d smax=%d)",sum,split,splitMax);
          for(int i=1;i<=LIMIT;i++){
               printf("%d",lens[i]);
          }
          printf(")\n");
     }
};

std::priority_queue<S> pq;
std::map<S,long double> memo;
std::set<S> addS;

void add_pq(S& s1){
     if(addS.find(s1)==addS.end()){
          addS.insert(s1);
          pq.push(s1);
     }
}

void split(S& s1){
     S s2;
     //まず分割してみる
   
     for(int i=1;i<=LIMIT;i++){
       
          if(i==1 && s1.lens[i]>0){
               //一個を分割しようとするので消える
               s2=s1;
               s2.sum--;
               s2.split--;
               s2.lens[i]--;
               if(memo.find(s2)==memo.end())memo[s2]=0;
               memo[s2]+=memo[s1]*s1.lens[i];
               add_pq(s2);
          }else if(i>2 && s1.lens[i]>0){
               //3個以上を分割しようとするので分割が一つ増える
             
               if(s2.split>s2.splitMax)s2.splitMax=s2.split;
               for(int j=1;j+1<i;j++){
                    s2=s1;
                    s2.sum--;
                    s2.lens[i]--;
                    s2.split++;
                    s2.lens[j]++;
                    s2.lens[i-j-1]++;
                    if(s2.splitMax<s2.split)s2.splitMax=s2.split;
                    if(memo.find(s2)==memo.end())memo[s2]=0;
                    memo[s2]+=memo[s1]*s1.lens[i];
                    add_pq(s2);
               }
          }
     }
     //分割数に変化がない場合の減らし方
     for(int i=2;i<=LIMIT;i++){
          s2=s1;
          s2.sum--;
          if(s1.lens[i]>0){
               s2.lens[i]--;
               s2.lens[i-1]++;
               if(memo.find(s2)==memo.end())memo[s2]=0;
               memo[s2]+=memo[s1]*s1.lens[i]*2;
               add_pq(s2);
          }
     }
}


int main(){
     clock_t start,end;
          start = clock();
   
     S s1;
   
     for(int i=0;i<=LIMIT;i++)s1.lens[i]=0;
     s1.sum=LIMIT;
     s1.splitMax=0;
     s1.split=0;
     s1.lens[LIMIT]=1;
   
     pq.push(s1);
     memo[s1]=1;
     long double anss[LIMIT+1]={0},all=0,ansSum=0;
   
     while(pq.empty()==false){
          s1=pq.top();
          pq.pop();
       
          if(s1.sum==1){
               anss[s1.splitMax+1]+=memo[s1];
          }else{
               split(s1);
          }
     }
     for(int i=0;i<=LIMIT;i++){
          std::cout<<"最大分割数"<<i<<"個"<<anss[i]<<"\n";
          all+=anss[i];
          ansSum+=anss[i]*i;
     }
     std::cout << std::setprecision(8);
     std::cout<<all<<" "<<ansSum<<" \nans="<<ansSum/all;
       
     end = clock();
     printf("\n%.2f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
}