AOJ 0540 あみだくじ

問題へのリンク

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("4 5 7 2");
            WillReturn.Add("20");
            WillReturn.Add("80");
            WillReturn.Add("100");
            WillReturn.Add("50");
            WillReturn.Add("1 1");
            WillReturn.Add("2 6");
            WillReturn.Add("2 3");
            WillReturn.Add("1 5");
            WillReturn.Add("3 1");
            WillReturn.Add("2 2 5 1");
            WillReturn.Add("10");
            WillReturn.Add("20");
            WillReturn.Add("1 1");
            WillReturn.Add("1 3");
            WillReturn.Add("0 0 0 0");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        int CurrInd = 0;
        while (true) {
            SplitAct(InputList[CurrInd]);
            mN = wkArr[0];
            mM = wkArr[1];
            mH = wkArr[2];
            mK = wkArr[3];
            mScoreDict.Clear();
            mEdgeList.Clear();

            if (mN == 0 && mM == 0 && mH == 0 && mK == 0) break;

            for (long I = CurrInd + 1; I <= CurrInd + mN; I++) {
                mScoreDict[mScoreDict.Count + 1] = long.Parse(InputList[(int)I]);
            }
            long LoopSta = CurrInd + mN + 1;
            long LoopEnd = CurrInd + mN + mM;

            for (long I = LoopSta; I <= LoopEnd; I++) {
                SplitAct(InputList[(int)I]);
                var WillAdd = new EdgeDef();
                WillAdd.Height = wkArr[1];
                WillAdd.FromNode = wkArr[0];
                WillAdd.ToNode = wkArr[0] + 1;
                WillAdd.ExChangeVal1 = null;
                WillAdd.ExChangeVal2 = null;
                mEdgeList.Add(WillAdd);
            }
            Solve();

            CurrInd += (int)(1 + mN + mM);
        }
    }

    static void Solve()
    {
        // 高さの昇順にソート
        mEdgeList = mEdgeList.OrderBy(pX => pX.Height).ToList();

        // 値[位置]なDict
        var ValDict = new Dictionary<long, long>();

        for (long I = 1; I <= mN; I++) {
            ValDict[I] = I;
        }

        for (long I = 0; I <= mEdgeList.Count - 1; I++) {
            long FromNode = mEdgeList[(int)I].FromNode;
            long ToNode = mEdgeList[(int)I].ToNode;

            long Val1 = ValDict[FromNode];
            long Val2 = ValDict[ToNode];

            mEdgeList[(int)I].ExChangeVal1 = Math.Min(Val1, Val2);
            mEdgeList[(int)I].ExChangeVal2 = Math.Max(Val1, Val2);

            // 三角交換
            long tmp = ValDict[FromNode];
            ValDict[FromNode] = ValDict[ToNode];
            ValDict[ToNode] = tmp;
        }

        // 基準スコアを求める
        long BaseScore = 0;
        foreach (var EachPair in ValDict) {
            if (EachPair.Value <= mK) {
                BaseScore += mScoreDict[EachPair.Key];
            }
        }
        var ScoreList = new List<long>() { BaseScore };

        // 位置[値]なDict
        var PosDict = new Dictionary<long, long>();
        foreach (var EachPair in ValDict) {
            PosDict[EachPair.Value] = EachPair.Key;
        }

        // 消す枝の全探索
        foreach (EdgeDef EachEdge in mEdgeList) {
            long CurrScore = BaseScore;

            long Val1 = EachEdge.ExChangeVal1.Value;
            long Val2 = EachEdge.ExChangeVal2.Value;

            long Pos1 = PosDict[Val1];
            long Pos2 = PosDict[Val2];

            if (Val1 <= mK) {
                CurrScore -= mScoreDict[Pos1];
                CurrScore += mScoreDict[Pos2];
            }
            if (Val2 <= mK) {
                CurrScore -= mScoreDict[Pos2];
                CurrScore += mScoreDict[Pos1];
            }
            ScoreList.Add(CurrScore);
        }
        Console.WriteLine(ScoreList.Min());
    }

    static long mN;
    static long mM;
    static long mH;
    static long mK;

    static Dictionary<long, long> mScoreDict = new Dictionary<long, long>();

    class EdgeDef
    {
        internal long Height;
        internal long FromNode;
        internal long ToNode;
        internal long? ExChangeVal1;
        internal long? ExChangeVal2;
    }
    static List<EdgeDef> mEdgeList = new List<EdgeDef>();
}

解説

あみだくじの横棒ごとに
どの値同士を交換したかを
覚えます。

1    2    3    4
|    |    |    |
| 12 |    | 34 |
|----|    |----|
|    | 14 |    |
|    |----|    |
| 24 |    | 13 |
|----|    |----|
|    | 23 |    |
|    |----|    |
|    |    |    |
4    3    2    1

枝ごとにSWAPした2つの値を記憶して、
あみだくじの一番下の値を求めます。

それから、
枝ごとに、SWAPしなかった場合の、
解候補を求めることができます。

類題

ABC279-E Cheating Amidakuji