ARC140-A Right String

問題へのリンク

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 1");
            WillReturn.Add("abac");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 0");
            WillReturn.Add("aaaaaaaaaa");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 1");
            WillReturn.Add("abcaba");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mS;
    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int K = wkArr[1];

        mS = InputList[1];
        UB = mS.Length - 1;

        // 約数を列挙する
        int[] YakusuuArr = DeriveYakusuuArr(mS.Length);
        foreach (int EachYakusuu in YakusuuArr) {
            int Cost = DeriveCost(EachYakusuu);
            if (Cost <= K) {
                Console.WriteLine(EachYakusuu);
                break;
            }
        }
    }

    // 分割数を引数として、コストを求める
    static int DeriveCost(int pSplitCnt)
    {
        // 文字のList[Mod] なDict
        var CharListDict = new Dictionary<int, List<char>>();

        for (int I = 0; I <= UB; I++) {
            int ModVal = I % pSplitCnt;

            if (CharListDict.ContainsKey(ModVal) == false) {
                CharListDict[ModVal] = new List<char>();
            }
            CharListDict[ModVal].Add(mS[I]);
        }

        int Cost = 0;
        foreach (List<char> EachCharList in CharListDict.Values) {
            // 最頻値以外のCount合計を集計
            var Query = EachCharList.GroupBy(pX => pX).OrderByDescending(pX => pX.Count()).Skip(1);
            foreach (var EachItem in Query) {
                Cost += EachItem.Count();
            }
        }
        return Cost;
    }

    // 約数を列挙する
    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;
    }
}

解説

3文字でローテートして2通りの文字列になるケースや
7文字でローテートして3通りの文字列になるケースなどを考えると
実現できないため

文字数の約数が、ローテートで作れる文字列のパターンとして
ありえる数だと分かります。

あとは、約数の昇順に実現可能かを試してます。