Submission #5699199

---

Source Code Expand

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
static int n = int.Parse(Console.ReadLine());
static int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
static double[] dp = new double[1<<16];
static long aim = 0;

	static void Main()
	{

    for(int i = 0; i < n; i++)
    {
      aim += (1<<nums[i]);
    }

    for(int i = 0; i < 1<<16; i++)
    {
      dp[i] = -1;
    }
    dp[0] = 0;//初期化

    Console.WriteLine(DP(aim));
	}

  static double DP(long rest)
  {
    if(dp[rest] != -1) return dp[rest];

    for(int i = 0; i < 14; i++)
    {
      if(((rest >> i)&1) == 1 || i == 13)
      {
        int changeCount = 0;
        if(((rest >> i)&1) == 1) changeCount++;
        if(((rest >> i+1)&1) == 1) changeCount++;
        if(((rest >> i+2)&1) == 1) changeCount++;
        dp[rest] = 0;
        
        if(changeCount == 3)
        {
          dp[rest] = 1;
          if(((rest >> i)&1) == 1) dp[rest] += (double)(DP(rest^(1<<i)))/3;
          if(((rest >> i+1)&1) == 1) dp[rest] += (double)(DP(rest^(1<<(i+1))))/3;
          if(((rest >> i+2)&1) == 1) dp[rest] += (double)(DP(rest^(1<<(i+2))))/3;
        }else if(changeCount == 2)
        {
          dp[rest] = (double)3/2;
          if(((rest >> i)&1) == 1) dp[rest] += (double)(DP(rest^(1<<i)))/2;
          if(((rest >> i+1)&1) == 1) dp[rest] += (double)(DP(rest^(1<<(i+1))))/2;
          if(((rest >> i+2)&1) == 1) dp[rest] += (double)(DP(rest^(1<<(i+2))))/2;
        }else if(changeCount == 1)
        {
          dp[rest] = 3;
          if(((rest >> i)&1) == 1) dp[rest] += (double)(DP(rest^(1<<i)));
          if(((rest >> i+1)&1) == 1) dp[rest] += (double)(DP(rest^(1<<(i+1))));
          if(((rest >> i+2)&1) == 1) dp[rest] += (double)(DP(rest^(1<<(i+2))));
        }else return dp[rest] = 0;
        break;
      }
    }
    //Console.WriteLine(DP(rest)+" "+rest);
    return dp[rest];
  }
}

Submission Info

Judge Result