ABC194-D Journey

問題へのリンク

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");
            //2.00000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            //4.50000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        decimal N = decimal.Parse(InputList[0]);

        decimal Answer = 0;
        for (decimal I = N - 1; 1M <= I; I--) {
            Answer += N / I;
        }
        Console.WriteLine(Answer);
    }
}

解説

頂点数が2の場合は、
訪問済が1ノード、未訪問が1ノード、から始まるので
未訪問ノードへの訪問確率は、0.5なので
期待値は0.5の逆数で2になります。

頂点数が3の場合は、
訪問済が1ノード、未訪問が2ノード、から始まるので
未訪問ノードへの訪問確率は、2/3なので

訪問済が2ノード、未訪問が1ノード
の状態になるまでの期待値は
2/3の逆数で1.5になります。
訪問済が2ノード、未訪問が1ノード、の状態からの期待値は
1/3の逆数で3ですので、
期待値の加法性より
解は1.5 + 3 = 4.5 になります。

頂点数が4の場合は、同様の手順で
4/3+4/2+4/1 で求まり、
頂点数が5の場合は、同様の手順で
5/4+5/3+5/2+5+5/1 で求まります。