第17回PAST K 正しいチェックディジット

問題へのリンク

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");
            WillReturn.Add("935?0");
            //Yes
            //93550
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("1?3?5");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1");
            WillReturn.Add("0");
            //Yes
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] SArr = InputList[1].ToCharArray();
        int UB = SArr.GetUpperBound(0);

        // カンマ区切り{前のmod10,現在の数字} [Ind,mod10]なDP表
        string[,] DPArr = new string[UB + 1, 10];
        for (int I = 0; I <= UB; I++) {
            for (int J = 0; J <= 9; J++) {
                DPArr[I, J] = "";
            }
        }

        for (int I = 0; I <= UB; I++) {
            var PrevModList = new List<int>();
            if (I == 0) {
                PrevModList.Add(0);
            }
            else {
                for (int J = 0; J <= 9; J++) {
                    if (DPArr[I - 1, J] != "") PrevModList.Add(J);
                }
            }

            foreach (int EachPrevMod in PrevModList) {
                if (SArr[I] == '?') {
                    var NewModSet = new HashSet<int>();
                    for (int J = 0; J <= 9; J++) {
                        int NewMod = (I + 1) * J + EachPrevMod;
                        NewMod %= 10;

                        if (NewModSet.Add(NewMod)) {
                            string DPInfo = string.Format("{0},{1}", EachPrevMod, J);
                            DPArr[I, NewMod] = DPInfo;
                        }
                    }
                }
                else {
                    int J = SArr[I] - '0';
                    int NewMod = (I + 1) * J + EachPrevMod;
                    NewMod %= 10;
                    string DPInfo = string.Format("{0},{1}", EachPrevMod, J);
                    DPArr[I, NewMod] = DPInfo;
                }
            }
        }

        if (DPArr[UB, 0] == "") {
            Console.WriteLine("No");
            return;
        }
        Console.WriteLine("Yes");

        // 復元処理
        int NeedMod = 0;
        var AnswerList = new List<int>();

        for (int I = UB; 0 <= I; I--) {
            string DPInfo = DPArr[I, NeedMod];
            string[] SplitArr = DPInfo.Split(',');
            int PrevMod10 = int.Parse(SplitArr[0]);
            int CurrVal = int.Parse(SplitArr[1]);

            AnswerList.Add(CurrVal);
            NeedMod = PrevMod10;
        }
        AnswerList.Reverse();
        var sb = new System.Text.StringBuilder();
        AnswerList.ForEach(pX => sb.Append(pX));
        Console.WriteLine(sb.ToString());
    }
}

解説

復元用の情報として、
カンマ区切り{前のmod10,現在の数字}
を状態に持ってDPし、
最後に復元してます。