ABC104-D We Love ABC

問題へのリンク

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("A??C");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("ABCBC");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("????C?????B??????A???????");
            //979596887
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;

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

        // 下記の状態番号で状態を管理
        // 状態0 文字を未選択
        // 状態1 文字Aを選択
        // 状態2 文字ABを選択
        // 状態3 文字ABCを選択

        // 場合の数[状態番号]なDP表
        long[] PrevDP = new long[4];
        PrevDP[0] = 1;

        foreach (char CurrChar in S) {
            long[] CurrDP = new long[4];
            for (int I = 0; I <= 3; I++) {
                if (PrevDP[I] == 0) continue;

                // 状態を維持する経路
                if (CurrChar == '?') {
                    CurrDP[I] += PrevDP[I] * 3;
                }
                else {
                    CurrDP[I] += PrevDP[I];
                }
                CurrDP[I] %= Hou;

                // 次の状態に遷移する経路
                if (I == 0 && (CurrChar == 'A' || CurrChar == '?')) {
                    CurrDP[1] += PrevDP[0];
                }
                if (I == 1 && (CurrChar == 'B' || CurrChar == '?')) {
                    CurrDP[2] += PrevDP[1];
                }
                if (I == 2 && (CurrChar == 'C' || CurrChar == '?')) {
                    CurrDP[3] += PrevDP[2];
                }
                CurrDP[I] %= Hou;
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[3]);
    }
}

解説

下記の状態番号で状態を管理するとし、
状態0 文字を未選択
状態1 文字Aを選択
状態2 文字ABを選択
状態3 文字ABCを選択

ABC?ACという文字列が入力されるとして、
空文字
A
AB
ABC?
ABC?A
ABC?AC
という順序で、1文字ずつ文字を処理したときの下記の場合の数の遷移をふまえて、
動的計画法を使ってます。

  N A B C ? A C
0 1 1 1 1 3 3 3
1 0 1 1 1 4 7 7
2 0 0 1 1 4 4 4
3 0 0 0 1 4 4 8