ABC182-C To 3

問題へのリンク

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("35");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("369");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6227384");
            //1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("11");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal string CurrStr;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string N = InputList[0];

        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.CurrStr = N;
        var Stk = new Stack<JyoutaiDef>();
        Stk.Push(WillPush);

        int UB = N.Length - 1;

        var AnswerKouhoList = new List<string>();

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

            AnswerKouhoList.Add(Popped.CurrStr);

            for (int I = Popped.CurrInd; I <= UB; I++) {
                WillPush.CurrInd = I + 1;
                WillPush.CurrStr = Popped.CurrStr.Remove(I, 1);
                WillPush.CurrStr = WillPush.CurrStr.Insert(I, "-");
                Stk.Push(WillPush);
            }
        }
        bool HasAnswer = false;
        int AnswerCnt = int.MaxValue;

        foreach (string EachStr in AnswerKouhoList) {
            if (EachStr.ToCharArray().All(pX => pX == '-')) {
                continue;
            }

            string ErasedStr = EachStr.Replace("-", "");

            int SumVal = ErasedStr.ToCharArray().Sum(pX => pX - '0');
            if (SumVal % 3 == 0) {
                HasAnswer = true;
                AnswerCnt = Math.Min(AnswerCnt, EachStr.ToCharArray().Count(pX => pX == '-'));
            }
        }
        if (HasAnswer) {
            Console.WriteLine(AnswerCnt);
        }
        else {
            Console.WriteLine(-1);
        }
    }
}

解説

18桁しかないので
2の18乗 = 262144
なので、深さ優先探索で全探索してます。