ARC141-A Periodic Number

問題へのリンク

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("3");
            WillReturn.Add("1412");
            WillReturn.Add("23");
            WillReturn.Add("498650499498649123");
            //1313
            //22
            //498650498650498650
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        foreach (string EachStr in InputList.Skip(1)) {
            long Result = Solve(long.Parse(EachStr));
            Console.WriteLine(Result);
        }
    }

    static long Solve(long pN)
    {
        string StrN = pN.ToString();
        int StrLen = StrN.Length;
        int UB = StrLen - 1;

        // 約数を全探索
        int[] YakusuuArr = DeriveYakusuuArr(StrLen);
        YakusuuArr = Array.FindAll(YakusuuArr, pX => pX < StrLen);

        var AnswerKouho = new List<long>();
        foreach (int EachYakusuu in YakusuuArr) {
            var StrList = new List<string>();

            for (int I = 0; I <= UB; I += EachYakusuu) {
                StrList.Add(StrN.Substring(I, EachYakusuu));
            }

            var LongList = new List<long>();
            StrList.ForEach(pX => LongList.Add(long.Parse(pX)));

            var sb = new System.Text.StringBuilder();
            while (sb.Length < StrLen) {
                sb.Append(LongList[0]);
            }
            long Kouho = long.Parse(sb.ToString());
            if (Kouho <= pN) {
                AnswerKouho.Add(Kouho);
            }

            if (Is10Beki(LongList[0])) {
                AnswerKouho.Add(long.Parse(new string('9', StrLen - 1)));
            }
            else {
                long MinusVal = LongList[0] - 1;
                sb.Length = 0;
                while (sb.Length < StrLen) {
                    sb.Append(MinusVal);
                }
                AnswerKouho.Add(long.Parse(sb.ToString()));
            }
        }
        return AnswerKouho.Max();
    }

    // 約数を列挙する
    static int[] DeriveYakusuuArr(int pTarget)
    {
        var YakusuuSet = new HashSet<int>();
        for (int I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }
        int[] YakusuuArr = YakusuuSet.ToArray();
        Array.Sort(YakusuuArr);
        return YakusuuArr;
    }

    // 10のべき乗かを判定する
    static bool Is10Beki(long pVal)
    {
        long CurrVal = 1;
        while (CurrVal <= pVal) {
            if (CurrVal == pVal) return true;
            CurrVal *= 10;
        }
        return false;
    }
}

解説

長さ12の文字列なら周期として考えられるのは
12の約数の中の12未満の数である
1,2,3,4,6
のいずれかになります。

周期ごとに、先頭の固まりでOKなら
先頭の固まりを解候補とし、
先頭の固まりでNGなら、
先頭の固まりから1引いた数を候補としてます。

ただし、先頭の固まりが10のべき乗の時は、
全体の文字数から1引いた長さの
連続した9が解候補になります。