AGC039-A Connection and Disconnection

問題へのリンク

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("issii");
            WillReturn.Add("2");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("qq");
            WillReturn.Add("81");
            //81
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("cooooooooonteeeeeeeeeest");
            WillReturn.Add("999993333");
            //8999939997
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];
        long K = long.Parse(InputList[1]);

        // 全部同じ文字なら等差数列にならない
        if (S.ToCharArray().Distinct().Count() == 1) {
            long StrLen = S.Length * K;
            Console.WriteLine(StrLen / 2);
            return;
        }

        var CntDict = new Dictionary<long, long>();
        string ConnS = "";
        for (int I = 1; I <= 10; I++) {
            ConnS += S;
            CntDict[I] = DeriveCnt(ConnS);
        }

        if (K <= 7) {
            Console.WriteLine(CntDict[K]);
            return;
        }

        long ModK = K % 3;
        if (ModK == 2) {
            long Kousuu = (K + 1) / 3;
            long Syokou = CntDict[2];
            long Kousa = CntDict[5] - CntDict[2];
            long Makkou = Syokou + Kousa * (Kousuu - 1);
            Console.WriteLine(Makkou);
        }
        if (ModK == 0) {
            long Kousuu = K / 3;
            long Syokou = CntDict[3];
            long Kousa = CntDict[6] - CntDict[3];
            long Makkou = Syokou + Kousa * (Kousuu - 1);
            Console.WriteLine(Makkou);
        }
        if (ModK == 1) {
            long Kousuu = (K - 1) / 3;
            long Syokou = CntDict[4];
            long Kousa = CntDict[7] - CntDict[4];
            long Makkou = Syokou + Kousa * (Kousuu - 1);
            Console.WriteLine(Makkou);
        }
    }

    // 文字列を引数として、同じ2文字が連続しないのに必要なReplace回数を返す
    static long DeriveCnt(string pStr)
    {
        long ReturnItem = 0;
        for (int I = 1; I <= pStr.Length - 1; I++) {
            if (pStr[I] == pStr[I - 1]) {
                ReturnItem++;
                I++;
            }
        }
        return ReturnItem;
    }
}

解説

まず、場合に分けます。

全ての文字が同じ場合は、
a       なら 0回必要
aa      なら 1回必要
aaa     なら 1回必要
aaaa    なら 2回必要
aaaaa   なら 2回必要
aaaaaa  なら 3回必要
aaaaaaa なら 3回必要

で(文字数 / 2) 回必要だと分かります。

全ての文字が同じでない場合で、両端が異なる場合、例えば
a???b と a???b
の場合は、Kを項番号とした等差数列になると分かります。

全ての文字が同じでない場合で、両端が同じ場合、例えば
a?b?a と a?b?a
の場合も、Kを項番号とした等差数列になりそうな気がします。

コーナーケースを踏みそうなので、
K=2からK=7までの解を求めて、
mod3で分類して、末項を求めてます。