AOJ 0604 IOI 列車で行こう

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

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("5 5");
            WillReturn.Add("OIOOI");
            WillReturn.Add("OOIOI");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 9");
            WillReturn.Add("IIIII");
            WillReturn.Add("IIIIIIIII");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static char[] SArr;
    static long SArr_UB;

    static char[] TArr;
    static long TArr_UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        SArr = InputList[1].ToCharArray();
        TArr = InputList[2].ToCharArray();

        SArr_UB = SArr.GetUpperBound(0);
        TArr_UB = TArr.GetUpperBound(0);

        mMemoArr = new long?[SArr_UB + 2, TArr_UB + 2, 2];

        long Answer = 0;
        for (long I = 0; I <= SArr_UB; I++) {
            for (long J = 0; J <= TArr_UB; J++) {
                if (SArr[I] == 'I' || TArr[J] == 'I') {
                    Answer = Math.Max(Answer, dfs(I, J, 'I'));
                }
            }
        }

        // 先頭と末尾は、Iでなくてはならない
        if (Answer >= 2 && Answer % 2 == 0) {
            Answer--;
        }
        Console.WriteLine(Answer);
    }

    static long?[, ,] mMemoArr;

    // SInd,TInd,次の文字を引数とし、作れる最長の文字列長を返す
    static long dfs(long pSInd, long pTInd, char pNextChar)
    {
        long LongNextChar = 0;
        if (pNextChar == 'I') LongNextChar = 1;

        if (mMemoArr[pSInd, pTInd, LongNextChar].HasValue) {
            return mMemoArr[pSInd, pTInd, LongNextChar].Value;
        }

        long Answer = 0;

        // 次がIの場合
        if (pNextChar == 'I') {
            if (pSInd <= SArr_UB && SArr[pSInd] == 'I') {
                Answer = Math.Max(Answer, 1 + dfs(pSInd + 1, pTInd, 'O'));
            }
            if (pTInd <= TArr_UB && TArr[pTInd] == 'I') {
                Answer = Math.Max(Answer, 1 + dfs(pSInd, pTInd + 1, 'O'));
            }
        }

        // 次がOの場合
        if (pNextChar == 'O') {
            if (pSInd <= SArr_UB && SArr[pSInd] == 'O') {
                Answer = Math.Max(Answer, 1 + dfs(pSInd + 1, pTInd, 'I'));
            }
            if (pTInd <= TArr_UB && TArr[pTInd] == 'O') {
                Answer = Math.Max(Answer, 1 + dfs(pSInd, pTInd + 1, 'I'));
            }
        }

        mMemoArr[pSInd, pTInd, LongNextChar] = Answer;

        return Answer;
    }
}

解説

メモ化再帰で解いてます。