幹事が楽な歓送迎会

幹事が楽な歓送迎会

締め切りが 2017/04/04 10:00 AM なので，その 1 分後に投稿されるように予約

設問

人事異動が多く発生する時期になりました。
歓送迎会などの飲み会などを開催したとき、幹事さんの悩みの種となるのがお釣りの準備です。
お釣りが出ないように参加者全員がちょうどの金額を用意してくれると助かるのですが、なかなかうまくいかないものです。

そこで、お釣りが不足しないような順番で会費を集めようと思っています。
例えば、会費が4000円のとき、千円札を出す人が1人いれば、五千円札を出す人が4人いても、
先に千円札の1人から受け付けると、残りの4人のためのお釣りを準備する必要がありません。

ここでは、会費が3000円のとき、千円札を出す人が m 人、五千円札を出す人が n 人いるものとします。
このとき、事前にお釣りを準備しなくても受け付けられる順番が何通りあるかを求めます。
ただし、出すお札の種類での順番についてのみ考え、どの人が出したかは問わないものとします。

例えば、m = 3, n = 2 のとき、以下の5通りがあります。
(1) 千円札 → 千円札 → 千円札 → 五千円札 → 五千円札
(2) 千円札 → 千円札 → 五千円札 → 千円札 → 五千円札
(3) 千円札 → 千円札 → 五千円札 → 五千円札 → 千円札
(4) 千円札 → 五千円札 → 千円札 → 千円札 → 五千円札
(5) 千円札 → 五千円札 → 千円札 → 五千円札 → 千円札

標準入力から参加者数が与えられるとき、m, nのすべての組み合わせについて、
事前にお釣りを準備しなくても受け付けられる順番が何通りあるかを求め、その和を標準出力に出力してください。
なお、参加者は「千円札を出す人」と「五千円札を出す人」のいずれかであるものとし、最大で32人までとします。

例えば、参加者数が5人のとき、m, n の組み合わせと、受け付けられる順番のパターン数は
以下の表のようになるため、12を出力します。

m     n     パターン数
0     5     0通り
1     4     0通り
2     3     2通り
3     2     5通り
4     1     4通り
5     0     1通り
合計       12通り

【入出力サンプル】
標準入力
5

標準出力
12

===================================

千円札と五千円札で支払う人 m 人， n 人とすると，すべての支払い方法は 2^N 通りある。
N = m+n 桁の 2 進数をビット列で表し，そのうちで条件を満たす場合をカウントする。
条件を満たす

f = function(N) {
    bincombinations = function(p) { # library(e1071) # N 桁のビット列
        retval = matrix(0, nrow = 2^p, ncol = p)
        for (n in 1:p) {
            retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))), length = 2^p)
        }
        retval
    }

    check = function(x) { # N 桁のビット列
        reservations = 0 # おつりに使える千円札の枚数
        for (i in seq_along(x)) { # ビット列の先端から順にチェック
            if (x[i] == 0) { # 千円札で支払った人
                reservations = reservations + 3 # 千円札が 3 枚殖える
            } else { # 五千円札で支払った人
                if (reservations < 2) { # お釣りに使える千円札が不足
                    return(FALSE)
                }
                reservations = reservations - 2 # お釣りで使うので千円札が 2 枚減る
            }
        }
        return(TRUE) # お釣りで使える千円札が不足することはなかった
    }

    a = bincombinations(N)
    b = apply(a, 1, check)
    n = rowSums(a)
    table(n, b)
}

例えば N=5 のときは
   b
n   FALSE TRUE
  0     0    1
  1     1    4
  2     5    5
  3     8    2
  4     5    0
  5     1    0
成功するのは b=TRUE のときで，n=0 のとき 1 回，n=1 のとき 4 回，n=2 のとき 5 回，n=3 のとき 2 回の，計 1+4+5+2=12 回である。
N=1,2,..., 20 について下図のような数表を作成する。



この数表の規則性は，a[1, 0] = a[2, 0] = a[2,1] = 1 で，a[N, n] = a[N-1, n-1] + a[N-1, n] である。
a[5, 1] = a[4, 0] + a[4, 1] = 1+3 = 4
パスカルの三角形を作る要領である。
ただし，各行で n に制約がある。n = 0.6*N+c(1,0.4, 0.8, 0.2, 0.6)[N %% 5+1] または floor(log10(10*(4^N)))
これを用いてプログラム化する。

f = function(N) {
    a = 1
    if (N >= 2) {
        for (i in 2:N) {
            a = (c(a, 0) + c(0, a))[1:floor(log10(10 * (4^i)))]
        }
    }
    sum(a)
}

> f(5)
[1] 12
> f(7)
[1] 44
> f(18)
[1] 73556
> f(28)
[1] 71886173
> f(32)
[1] 1143455572
> system.time(f(32))
   ユーザ   システム       経過  
     0.019      0.001      0.010