ABC011-D 大ジャンプ

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 10000000");
            WillReturn.Add("10000000 10000000");
            //0.125
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("100 2");
            WillReturn.Add("3 7");
            //0.0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11 8562174");
            WillReturn.Add("25686522 17124348");
            //0.018174648284912
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        decimal[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => decimal.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        decimal N = wkArr[0];
        decimal D = wkArr[1];

        SplitAct(InputList[1]);
        decimal X = wkArr[0];
        decimal Y = wkArr[1];

        if (X % D != 0 || Y % D != 0) {
            Console.WriteLine(0M);
            return;
        }
        X /= D;
        Y /= D;

        // ゴールはプラスにしておく
        X = Math.Abs(X);
        Y = Math.Abs(Y);

        decimal Answer = 0M;
        for (decimal I = 0; I <= N; I++) {
            //X方向に移動する回数
            decimal MoveXCnt = I;

            //Y方向に移動する回数
            decimal MoveYCnt = N - I;

            bool CanMove1;
            decimal PlusCnt1;
            decimal MinusCnt1;
            DeriveCanMove(X, MoveXCnt, out CanMove1, out PlusCnt1, out MinusCnt1);

            bool CanMove2;
            decimal PlusCnt2;
            decimal MinusCnt2;
            DeriveCanMove(Y, MoveYCnt, out CanMove2, out PlusCnt2, out MinusCnt2);

            if (CanMove1 == false || CanMove2 == false) {
                continue;
            }
            if (N < 30) {
                decimal CurrProb = DeriveCombi(N, PlusCnt1);
                CurrProb *= DeriveCombi(N - PlusCnt1, MinusCnt1);
                CurrProb *= DeriveCombi(N - PlusCnt1 - MinusCnt1, PlusCnt2);

                CurrProb *= (decimal)(Math.Pow(1D / 4D, (double)(N)));
                Answer += CurrProb;
            }
            else {
                double CurrProbLog10 = DeriveCombiLog10(N, PlusCnt1);
                CurrProbLog10 += DeriveCombiLog10(N - PlusCnt1, MinusCnt1);
                CurrProbLog10 += DeriveCombiLog10(N - PlusCnt1 - MinusCnt1, PlusCnt2);
                CurrProbLog10 += (double)N * Math.Log10(1D / 4D);
                Answer += (decimal)(Math.Pow(10, CurrProbLog10));
            }
        }
        Console.WriteLine(Answer);
    }

    // 目標座標と移動回数を引数として、
    // 到達可否とプラスの移動回数とマイナスの移動回数を返す
    static void DeriveCanMove(decimal pGoalPos, decimal pMoveCnt,
        out bool pCanMove, out decimal pPlusCnt, out decimal pMinusCnt)
    {
        pCanMove = true;
        pPlusCnt = pGoalPos;
        pMinusCnt = 0M;

        // 移動回数が不足している場合
        if (pMoveCnt < pGoalPos) {
            pCanMove = false;
            return;
        }

        decimal RestCnt = pMoveCnt - pGoalPos;

        // 偶数でなかったらNG
        if (RestCnt % 2 > 0) {
            pCanMove = false;
            return;
        }

        pPlusCnt += RestCnt / 2;
        pMinusCnt += RestCnt / 2;
    }

    // nCrを求める
    static decimal DeriveCombi(decimal pN, decimal pR)
    {
        decimal WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        var DivList = new List<decimal>();
        for (decimal I = 2; I <= pR; I++) {
            DivList.Add(I);
        }

        for (decimal I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;

            for (int J = DivList.Count - 1; 0 <= J; J--) {
                if (WillReturn % DivList[J] == 0) {
                    WillReturn /= DivList[J];
                    DivList.RemoveAt(J);
                }
            }
        }
        return WillReturn;
    }

    // nCrのLog10を求める
    static double DeriveCombiLog10(decimal pN, decimal pR)
    {
        double WillReturn = 0;
        pR = Math.Min(pR, pN - pR);

        for (decimal I = 2; I <= pR; I++) {
            WillReturn -= Math.Log10((double)I);
        }

        for (decimal I = pN - pR + 1; I <= pN; I++) {
            WillReturn += Math.Log10((double)I);
        }
        return WillReturn;
    }
}

解説

まず、ゴールの座標がDの倍数かを判定します。
Dの倍数でなかったら、到達確率は0になります。

Dの倍数の場合は、
左右の移動回数と、上下の移動回数の組み合わせを全探索します。

到達可能な場合は、残りの移動回数も、求めます。
左に2回、右に3回、上に2回、下に3回が解だとすると
←←→→→↑↑↓↓↓
の順不同での確率を求めればいいので

10C2 * (1/4)の2乗 *
 8C3 * (1/4)の3乗 *
 5C2 * (1/4)の2乗 *
 3C3 * (1/4)の3乗
が確率を求める計算式になります。

確率を順に求めて、確率の加法定理で足していけば
解が求まりますが、
Nが大きいとオーバーフローするので、
Nの値によって、対数を使う方法と使わない方法を、使い分けてます。