Search on the blog

2013年4月29日月曜日

非減少列の数

この前のCode Jamの問題で、非減少列の数って意外と少ないんだなと思ったので、どれくらいあるのか調べてみた。

せっかくなので、問題を設定して解いてみることにする。

{0,1,...,9}からなる長さNの列Aのうち、Ai <= Ai+1となるものの個数を求めよ。

まあ普通に考えると、DPだよね。

import java.util.Scanner;

public class Main {
 Scanner sc = new Scanner(System.in);
 
 public static void main(String[] args) {
  new Main().solve();
 }
 
 public void solve() {
  int N = sc.nextInt();
  
  long[][] dp = new long[N+1][10];
  dp[0][0] = 1;
  
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < 10; j++)
    for (int k = j; k < 10; k++)
     dp[i+1][k] += dp[i][j];
  }
  
  long ret = 0;
  for (int i = 0; i < 10; i++)
   ret += dp[N][i];
  
  System.out.println(ret);
  
 }
}

しかしよくよく考えると、組み合わせ論を使って解けるな。ということで以下の式を導き出した。

これを実装すると、以下のようになる。(多倍長整数が面倒いのでPythonで。)

def fact(x):
    if x < 2:
        return 1
    return x * fact(x-1)

def comb(x, y):
    return fact(x) / fact(x-y) / fact(y)

def homog(x, y):
    return comb(x+y-1, y)

def solve(n):
    return sum ([comb(10, x) * homog(x, n - x) for x in range(1, min(10, n)+1)])

if __name__ == "__main__":
    n = int(raw_input())
    print solve(n)

DP解を使って検算したので、多分導いた式は正しいと思う。(追記: いや何やってんだ。これ。10Hnでおしまいじゃん!)

で、以下が長さNの非減少列の個数。非減少じゃないものも合わせた列の個数は10Nだけど、それに比べるとずっと小さい数におさまっている。

N 個数
5 2002
10 92378
15 1307504
20 10015005
25 52451256
30 211915132
うーん、なんか感覚的にすっきりしないな。
今見ている要素より上にいく確率を1/2、下にいく確率を1/2とすると、ずっと上に行きつづける確率は(1/2)Nで、これだとパターン数がおよそ5Nだけど、実際はこれよりもっと小さい。
いや違う、上に行きつづけるからどんどん数字が大きくなってきて最終的には、上に行く確率が(1/10)に近づくわけか。そう考えると納得できる気がする。

0 件のコメント:

コメントを投稿