ＡＫＢ４８生写真 「全部集めなきゃ意味がない！」 最低１７２冊＝４３万円

http://www.akibablog.net/archives/2008/03/akb48-080319.html

どうして人はコンプを目指すのだろうか。よく分からない。
私は小学生のときに漢和辞典に載っている漢字を全部書こうとして、なぜか最後のほうでやめてしまった。
以来、コンプと呼べるようなことをしたことがないような気がする。
「桜満開」もGW編を入れると、何気に6公演中5公演鑑賞だったし。

それはおいといて、ネタの提供を忘れないでくれる。
写真集1種類につき212種類の生写真が用意されていて、1冊につき5枚がランダムに封入されている。
問題なのは、5枚がダブリなしに封入されているかどうかだが、
現実問題として、そこまでチェックはできないのではないだろうか。
だから、ダブリはあると考える。
そうすると前の問題とだいたい同じになる。

写真をランダムに1枚ずつとっていくと、
212種類揃うまでに平均1258.466枚とることになる。
すなわち、写真集を約252冊買うことになる。
それが4種類あるから、
約1000冊購入することになる。

もうちょっとちゃんとみてみよう。
写真集を購入する冊数は、写真をとる枚数を5で割って切上げになる。
これを考慮して計算すると、
平均1004.37冊となった。

#include 
using namespace std;
const int   nMembers = 212;

const int   limit = 25000;

const int   limit_book = limit / 5;
int min(int a, int b) { return a < b ? a : b; }
void main() {

    const int   N = nMembers;

    

    double  p[limit+1];

    p[0] = 1;

    double  p_n[limit+1];

    double  p_next[limit+1];

    for(int n = 0; n < N; n++) {

        int     climit = limit;

        p_n[1] = (N - n) / (double)N;

        for(int i = 2; i <= limit; i++) {

            p_n[i] = p_n[i-1] * n / N;

            if(p_n[i] < 1e-100) {

                climit = i - 1;

                break;

            }

        }

        

        for(int i = 0; i <= limit; i++) {

            p_next[i] = 0;

        }

        for(int i = n; i <= limit; i++) {

            if(p[i] < 1e-200)

                break;

            for(int k = 1; k <= min(limit - i, climit); k++) {

                p_next[i+k] += p[i] * p_n[k];

            }

        }

        

        for(int i = 0; i <= limit; i++) {

            p[i] = p_next[i];

        }

    }

    

    // pを生写真から写真集に変換

    for(int i = 1; i <= limit_book; i++) {

        double  a = 0;

        for(int k = i * 5 + 1; k <= i * 5 + 5; k++) {

            a += p[k];

        }

        p[i] = a;

    }

    

    double  q[limit+1];

    for(int i = 0; i <= limit_book; i++) {

        q[i] = 0;

    }

    for(int i = 0; i <= limit_book; i++) {

        for(int k = 0; k <= limit_book - i; k++) {

            q[i+k] += p[i] * p[k];

        }

    }

    

    double  r[limit+1];

    for(int i = 0; i <= limit_book; i++) {

        r[i] = 0;

    }

    for(int i = 0; i <= limit_book; i++) {

        for(int k = 0; k <= limit_book - i; k++) {

            r[i+k] += q[i] * q[k];

        }

    }

    

    for(int n = (N + 4) / 5 * 4; n <= limit_book; n++) {

        printf("%d %10g\n", n, r[n]);

    }

}