ABC131-E Friendships

問題へのリンク

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

    struct EdgeDef
    {
        internal int FromNode;
        internal int ToNode;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];
        long K = wkArr[1];

        // ノード数が2で、スター型にできない場合
        if (N == 2 && K == 0) {
            Console.WriteLine(1);
            Console.WriteLine("1 2");
            return;
        }
        if (N == 2 && K == 1) {
            Console.WriteLine(-1);
            return;
        }

        // ノード数が3以上なら、ノード1を中央として、スター型のグラフを構築
        long Cost2PairCnt = DeriveChoose(N - 1, 2);

        if (Cost2PairCnt < K) {
            Console.WriteLine(-1);
            return;
        }

        // ノード1との無向辺を貼る
        var EdgeList = new List<EdgeDef>();
        for (int I = 2; I <= N; I++) {
            EdgeDef WillAdd;
            WillAdd.FromNode = 1;
            WillAdd.ToNode = I;
            EdgeList.Add(WillAdd);
        }

        // 無向辺を貼って、コスト2のノードペアの数を調整
        for (int I = 2; I <= N; I++) {
            for (int J = I + 1; J <= N; J++) {
                if (Cost2PairCnt > K) {
                    EdgeDef WillAdd;
                    WillAdd.FromNode = I;
                    WillAdd.ToNode = J;
                    EdgeList.Add(WillAdd);
                    Cost2PairCnt--;
                }
            }
        }

        Console.WriteLine(EdgeList.Count);
        foreach (EdgeDef EachEdge in EdgeList) {
            Console.WriteLine("{0} {1}", EachEdge.FromNode, EachEdge.ToNode);
        }
    }

    // nCr を求める
    static long DeriveChoose(long pN, long pR)
    {
        if (pN < pR) return 0;

        pR = Math.Min(pR, pN - pR);

        long WillReturn = 1;
        for (long I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
        }
        for (long I = 2; I <= pR; I++) {
            WillReturn /= I;
        }
        return WillReturn;
    }
}

解説

場合分けを行い
ノード数が2の場合に対応してます。

ノード数が3以上の場合は、
最短距離が2になるノードのペア数が最小になるのは、
完全グラフの場合で、0になります。
最短距離が2になるノードのペア数が最大になるのは、
スター型グラフの場合で、ノード数をnとすると
(n-1)C2 になります。