AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC198-D Send More Money


問題へのリンク


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("a");
            WillReturn.Add("b");
            WillReturn.Add("c");
            //1
            //2
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("x");
            WillReturn.Add("x");
            WillReturn.Add("y");
            //1
            //1
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("p");
            WillReturn.Add("q");
            WillReturn.Add("p");
            //UNSOLVABLE
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("abcd");
            WillReturn.Add("efgh");
            WillReturn.Add("ijkl");
            //UNSOLVABLE
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("send");
            WillReturn.Add("more");
            WillReturn.Add("money");
            //9567
            //1085
            //10652
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB_X;
    static int UB_Y;
    static HashSet<char> mNonUseZeroSet = new HashSet<char>();

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

        string S1 = InputList[0];
        string S2 = InputList[1];
        string S3 = InputList[2];

        var AppearCharSet = new HashSet<char>();
        AppearCharSet.UnionWith(S1);
        AppearCharSet.UnionWith(S2);
        AppearCharSet.UnionWith(S3);

        // 1対1に対応するので、10文字以上あったらNG
        if (AppearCharSet.Count > 10) {
            Console.WriteLine("UNSOLVABLE");
            return;
        }

        // 0を使えないcharのSet
        mNonUseZeroSet.Add(S1[0]);
        mNonUseZeroSet.Add(S2[0]);
        mNonUseZeroSet.Add(S3[0]);

        // 前ゼロを補完する
        int MaxLen = Math.Max(S1.Length, S2.Length);
        MaxLen = Math.Max(MaxLen, S3.Length);

        S1 = S1.PadLeft(MaxLen, '0');
        S2 = S2.PadLeft(MaxLen, '0');
        S3 = S3.PadLeft(MaxLen, '0');

        // 二次元配列を作成
        var StringList = new List<string>() { S1, S2, S3 };
        char[,] BanArr = CreateBanArr(StringList);
        UB_X = BanArr.GetUpperBound(0);
        UB_Y = BanArr.GetUpperBound(1);

        Solve(BanArr);
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal char[,] BanArr;
        internal HashSet<char> UseNumSet;
    }

    static void Solve(char[,] pBanArr)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = UB_X;
        WillPush.CurrY = 0;
        WillPush.BanArr = pBanArr;
        WillPush.UseNumSet = new HashSet<char>();
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // 繰り上がりの対応
            if (Popped.CurrY > UB_Y) {
                // 無効な盤面なら枝切り
                if (IsValid(Popped.BanArr, Popped.CurrX, true) == false) {
                    continue;
                }
                Popped.CurrX--;
                Popped.CurrY = 0;
            }
            if (Popped.CurrX < 0) {
                if (IsValid(Popped.BanArr, 0, false)) {
                    PrintAnswer(Popped.BanArr);
                    return;
                }
                continue;
            }

            char CurrChar = Popped.BanArr[Popped.CurrX, Popped.CurrY];

            WillPush.CurrX = Popped.CurrX;
            WillPush.CurrY = Popped.CurrY + 1;

            // 既に決定している場合
            if ('0' <= CurrChar && CurrChar <= '9') {
                WillPush.BanArr = Popped.BanArr;
                WillPush.UseNumSet = Popped.UseNumSet;
                Stk.Push(WillPush);
                continue;
            }
            // 未決定の文字の場合
            for (char I = '0'; I <= '9'; I++) {
                if (Popped.UseNumSet.Contains(I)) continue;
                if (I == '0' && mNonUseZeroSet.Contains(CurrChar)) continue;

                char[,] NewBanArr = (char[,])Popped.BanArr.Clone();
                for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                    for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                        if (NewBanArr[LoopX, LoopY] == CurrChar) {
                            NewBanArr[LoopX, LoopY] = I;
                        }
                    }
                }
                WillPush.BanArr = NewBanArr;
                WillPush.UseNumSet = new HashSet<char>(Popped.UseNumSet);
                WillPush.UseNumSet.Add(I);
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine("UNSOLVABLE");
    }

    // 盤面を引数として解を出力する
    static void PrintAnswer(char[,] pBanArr)
    {
        Func<int, string> GetLineAllStrFunc = pY =>
        {
            var CharList = new List<char>();
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                CharList.Add(pBanArr[LoopX, pY]);
            }
            return new string(CharList.ToArray());
        };
        string S1 = GetLineAllStrFunc(0);
        string S2 = GetLineAllStrFunc(1);
        string S3 = GetLineAllStrFunc(2);

        // 前ゼロは消す
        S1 = Regex.Replace(S1, "^0+", "");
        S2 = Regex.Replace(S2, "^0+", "");

        Console.WriteLine(S1);
        Console.WriteLine(S2);
        Console.WriteLine(S3);
    }

    // XStaIndからUB_Xまでの、足し算で、有効盤面かを返す
    static bool IsValid(char[,] pBanArr, int pXStaInd, bool pEnableCut)
    {
        int StrLen = UB_X - pXStaInd + 1;

        Func<int, string> GetLinePartStrFunc = pY =>
        {
            var CharList = new List<char>();
            for (int LoopX = pXStaInd; LoopX <= UB_X; LoopX++) {
                CharList.Add(pBanArr[LoopX, pY]);
            }
            return new string(CharList.ToArray());
        };

        string S1 = GetLinePartStrFunc(0);
        string S2 = GetLinePartStrFunc(1);
        string S3 = GetLinePartStrFunc(2);

        long S1Long = long.Parse(S1);
        long S2Long = long.Parse(S2);
        long S3Long = long.Parse(S3);

        // 指定桁に10進数をカットする
        Func<int, long, long> CutFunc = (pKeta, pVal) =>
        {
            if (pKeta == 1) return pVal % 10;
            if (pKeta == 2) return pVal % 100;
            if (pKeta == 3) return pVal % 1000;
            if (pKeta == 4) return pVal % 10000;
            if (pKeta == 5) return pVal % 100000;
            if (pKeta == 6) return pVal % 1000000;
            if (pKeta == 7) return pVal % 10000000;
            if (pKeta == 8) return pVal % 100000000;
            if (pKeta == 9) return pVal % 1000000000;
            return pVal % 10000000000;
        };

        long Sum = S1Long + S2Long;

        // 指定桁までしか見ない場合
        if (pEnableCut) {
            Sum = CutFunc(StrLen, Sum);
            S3Long = CutFunc(StrLen, S3Long);
        }
        return Sum == S3Long;
    }

    // stringのListをcharの2次元配列に設定する
    static char[,] CreateBanArr(List<string> pStringList)
    {
        if (pStringList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = pStringList[0].Length - 1;
        int UB_Y = pStringList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = pStringList[Y][X];
            }
        }
        return WillReturn;
    }

    // 2次元配列のデバッグ出力
    static void PrintBan(char[,] pBanArr)
    {
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                Console.Write(pBanArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}


解説

前ゼロを付与してから
長方形の2次元配列と見なして、
下位桁から数字を決めつつ、
桁ごとに、枝切りしてます。