AtCoderの企業コンテスト    次の企業コンテストの問題へ    前の企業コンテストの問題へ

diverta 2019 Programming Contest C AB Substrings


問題へのリンク


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("ABCA");
            WillReturn.Add("XBAZ");
            WillReturn.Add("BAD");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9");
            WillReturn.Add("BEWPVCRWH");
            WillReturn.Add("ZZNQYIJX");
            WillReturn.Add("BAVREA");
            WillReturn.Add("PA");
            WillReturn.Add("HJMYITEOX");
            WillReturn.Add("BCJHMRMNK");
            WillReturn.Add("BP");
            WillReturn.Add("QVFABZ");
            WillReturn.Add("PRGKSPUNA");
            //4
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7");
            WillReturn.Add("RABYBBE");
            WillReturn.Add("JOZ");
            WillReturn.Add("BMHQUVA");
            WillReturn.Add("BPA");
            WillReturn.Add("ISU");
            WillReturn.Add("MCMABAOBHZ");
            WillReturn.Add("SZMEHMA");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] SArr = InputList.Skip(1).ToArray();

        // 元からあるABの数
        int BaseCnt = 0;
        foreach (string EachS in SArr) {
            for (int I = 1; I <= EachS.Length - 1; I++) {
                if (EachS[I - 1] == 'A' && EachS[I] == 'B') {
                    BaseCnt++;
                }
            }
        }

        int FirstB_Cnt = 0;
        int LastA_Cnt = 0;
        int FirstB_LastA_Cnt = 0;
        foreach (string EachS in SArr) {
            bool FirstB = EachS.StartsWith("B");
            bool LastA = EachS.EndsWith("A");

            if (FirstB && LastA) {
                FirstB_LastA_Cnt++;
            }
            else if (FirstB) {
                FirstB_Cnt++;
            }
            else if (LastA) {
                LastA_Cnt++;
            }
        }

        // 文字列結合で作ったABの数
        int ConcatCnt = DeriveConcatCnt(FirstB_Cnt, LastA_Cnt, FirstB_LastA_Cnt);

        Console.WriteLine(BaseCnt + ConcatCnt);
    }

    // 結合して作成できるABの数を返す
    static int DeriveConcatCnt(int pFirstB_Cnt, int pLastA_Cnt, int pFirstB_LastA_Cnt)
    {
        int ConcatCnt = 0;
        if (pLastA_Cnt == 0 && pFirstB_LastA_Cnt == 0) {
            return 0;
        }

        // pFirstB_LastA_Cntが1以上だったら、最初に全部使う
        if (pFirstB_LastA_Cnt > 0) {
            if (pLastA_Cnt > 0) {
                pLastA_Cnt--;
            }
            else {
                pFirstB_LastA_Cnt--;
            }

            if (pFirstB_LastA_Cnt > 0) {
                // 全部使って、次のBの分も処理しておく
                ConcatCnt += pFirstB_LastA_Cnt;
                if (pFirstB_Cnt > 0) {
                    ConcatCnt++;
                    pFirstB_Cnt--;
                }
            }
            else if (pFirstB_Cnt > 0) {
                ConcatCnt++;
                pFirstB_Cnt--;
            }
            else {
                return 0;
            }
        }
        ConcatCnt += Math.Min(pFirstB_Cnt, pLastA_Cnt);
        return ConcatCnt;
    }
}


解説

必ず作成できるABと、文字列結合でできるABを分けて考えてます。
文字列結合でできるABは、

●先頭がBな文字列
●最後がAな文字列
●先頭がB、かつ、最後がAな文字列
の3つの文字列の個数で、場合分けしてます。