ABC274-E Booster

問題へのリンク

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 1");
            WillReturn.Add("1 1");
            WillReturn.Add("0 1");
            WillReturn.Add("1 0");
            //2.5000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1");
            WillReturn.Add("1 1");
            WillReturn.Add("0 1");
            WillReturn.Add("100 0");
            //3.4142135624
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 2");
            WillReturn.Add("4 4");
            WillReturn.Add("1 0");
            WillReturn.Add("0 1");
            //4.3713203436
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ObjectInfoDef
    {
        internal double X;
        internal double Y;
    }
    static ObjectInfoDef[] mObjectInfoArr;

    static int mMuraCnt;
    static int mTakaraCnt;

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

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

        SplitAct(InputList[0]);

        mMuraCnt = wkArr[0];
        mTakaraCnt = wkArr[1];

        var ObjectInfoList = new List<ObjectInfoDef>();

        ObjectInfoDef StaNode;
        StaNode.X = 0D;
        StaNode.Y = 0D;
        ObjectInfoList.Add(StaNode);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ObjectInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            ObjectInfoList.Add(WillAdd);
        }
        mObjectInfoArr = ObjectInfoList.ToArray();
        Solve();
    }

    static void Solve()
    {
        int ArrLen = mObjectInfoArr.Length;
        int AllBitOn = (1 << ArrLen) - 1;

        // 最小コスト[訪問済ノードセット ,現在ノード ] なDP表
        double?[,] DPArr = new double?[AllBitOn + 1, ArrLen + 1];
        DPArr[0, 0] = 0;

        string BitStr1 = new string('0', mTakaraCnt) + new string('1', 1 + mMuraCnt);
        string BitStr2 = new string('1', mTakaraCnt) + new string('0', 1 + mMuraCnt);
        int BitSet1 = Convert.ToInt32(BitStr1, 2);
        int BitSet2 = Convert.ToInt32(BitStr2, 2);

        // 数値[PopCount]なDict
        var ListDict = new Dictionary<int, List<int>>();
        for (int I = 0; I <= AllBitOn; I++) {
            int CurrPopCount = PopCount(I);
            if (ListDict.ContainsKey(CurrPopCount) == false) {
                ListDict[CurrPopCount] = new List<int>();
            }
            ListDict[CurrPopCount].Add(I);
        }

        double Answer = double.MaxValue;
        for (int I = 1; I <= ArrLen; I++) {
            for (int J = 0; J <= mObjectInfoArr.GetUpperBound(0); J++) {
                // 枝切り
                if (J == 0 && I < mMuraCnt) continue;

                // ビットシフトする必要あり
                int JBit = (1 << J);

                foreach (int K in ListDict[I - 1]) {
                    // 再訪は不可
                    if ((K & JBit) > 0) continue;

                    for (int L = 0; L <= ArrLen - 1; L++) {
                        if (DPArr[K, L].HasValue == false) continue;

                        int NewK = K | JBit;
                        int NewL = J;

                        // 宝の数
                        int TakaraCnt = PopCount(K & BitSet2);

                        double NewVal = DPArr[K, L].Value;
                        double XDiff = mObjectInfoArr[J].X - mObjectInfoArr[L].X;
                        double YDiff = mObjectInfoArr[J].Y - mObjectInfoArr[L].Y;
                        double Distance = Math.Sqrt(XDiff * XDiff + YDiff * YDiff);
                        Distance /= Math.Pow(2, TakaraCnt);
                        NewVal += Distance;
                        if (DPArr[NewK, NewL].HasValue) {
                            if (DPArr[NewK, NewL].Value <= NewVal) {
                                continue;
                            }
                        }
                        // クリア状態ならDP表は更新しない
                        if (NewL == 0) {
                            if ((NewK & BitSet1) == BitSet1) {
                                Answer = Math.Min(Answer, NewVal);
                                continue;
                            }
                        }

                        DPArr[NewK, NewL] = NewVal;
                    }
                }
            }
        }
        Console.WriteLine(Answer);
    }

    ////////////////////////////////////////////////////////////////
    // C++のPopCount
    ////////////////////////////////////////////////////////////////
    static int PopCount(int pVal)
    {
        int WillReturn = 0;
        while (pVal > 0) {
            if (pVal % 2 == 1) WillReturn++;
            pVal /= 2;
        }
        return WillReturn;
    }
}

解説

数値[PopCount]なDictを前処理で作成してから、
TSP問題として解いてます。