Submission #7465721

---

Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

//参考(http://sucrose.hatenablog.com/entry/2015/01/25/232628)
namespace AtCoder
{
    class Program
    {
        static long[] Sarray() { return ReadLine().Trim().Split().Select(long.Parse).ToArray(); }
        static List<long> Slist() { return ReadLine().Trim().Split().Select(long.Parse).ToList(); }

        //組み合わせ
        public class Combination
        {
            double[,] dp;
            public Combination(long n)
            {
                dp = new double[n+1, n+1];
                for(var i=0;i<n+1;++i)
                {
                    dp[i, 0] = 1;
                    dp[i, i] = 1;
                }
                for (var i = 2; i < n + 1; ++i)
                    for (var j = 1; j < i; ++j)
                        dp[i, j] = dp[i - 1, j - 1] + dp[i - 1, j];
            }
            public double com(int n, int k)
            {
                if (n < k) return 0;
                if (n < 0 | k < 0) return 0;
                return dp[n, k];
            }
        }
        static void Main(string[] args)
        {
            var N = Sarray()[0];
            var e = new double[N + 1];
            var cmb = new Combination(N+1);
            for (var i = 2; i <= N; ++i)
            {
                var p = new double[i];
                for (var k = 1; k < i; ++k)
                {
                    double cst = 3.0 * cmb.com(i, k) / Math.Pow(3, i);
                    double p1 = ((k < i - k) ? 2 : 0) * cst;
                    double p2 = ((i - 2 * k == 0 || k < i - 2 * k) ? cmb.com(i - k, k) : 0) * cst;
                    double p3 = 0;
                    for (var m = k + 1; m <= i - 2 * k - 1; ++m)
                        p3 += cmb.com(i - k, m) * cst;
                    p[k] = p1 + p2 + p3;
                }
                for (var k = 1; k < i; ++k)
                    e[i] += e[k] * p[k];
                e[i] = (e[i] + 1) / p.Sum();
            }
            WriteLine(e[N]);
        }
    }
}

Submission Info

Judge Result