Problem158 左隣の文字より辞書順で後になる文字

問題

26文字のアルファベットから3個の異なった文字を取ると, 長さ3の文字列を作ることができる.
例えば, 'abc', 'hat', 'zyx'となる.

この3つの例について調べると, 'abc'は左隣の文字より辞書順で後になる文字が2個ある.
'hat'では, 左隣の文字より辞書順で後になる文字がちょうど1個となり,
'zyx'では0個となる.

左隣の文字より辞書順で後になる文字がちょうど1個となるような長さ3の文字列は全部で10400個存在する.

いま, n <= 26個の異なった文字について考える.
nについて, p(n) を左隣の文字より辞書順で後になる文字がちょうど1個となるような長さnの文字列の個数であるとする.

p(n) の最大値を求めよ.

ソース

using System;

class Program
{
    static void Main()
    {
        long Answer = long.MinValue;
        for (int I = 1; I <= 26; I++) {
            long wkLong = Solve(I);
            Console.WriteLine("pN({0})={1}", I, wkLong);
            if (Answer < wkLong)
                Answer = wkLong;
        }
        Console.WriteLine("解は{0}", Answer);
    }

    static long Solve(int pN)
    {
        long WillReturn = 0;

        //単調増加になる文字の組み合わせ
        for (char I = 'A'; I <= 'Z'; I++) {
            for (char J = (char)(I + 1); J <= 'Z'; J++) {
                //単調増加になった位置
                for (int K = 2; K <= pN; K++) {
                    WillReturn += DerivePatternCnt(I, J, K, pN);
                }
            }
        }
        return WillReturn;
    }

    //単調増加な文字の組み合わせと増加した位置を引数として、場合の数を返す
    static long DerivePatternCnt(char pChar1, char pChar2, int pK, int pN)
    {
        bool HasLeftSpace = pK > 2;
        bool HasRightSpace = pK < pN;

        int LeftKouhoCnt = 'Z' - pChar1;
        LeftKouhoCnt--; //pChar2の分
        int RightKouhoCnt = pChar2 - 'A';
        RightKouhoCnt--; //pChar1の分

        int LeftNeedCnt = pK - 2;
        int RightNeedCnt = pN - pK;

        if (HasLeftSpace == false && HasRightSpace == false) {
            return 1;
        }
        if (HasLeftSpace == false && HasRightSpace) {
            if (RightNeedCnt <= RightKouhoCnt) return DeriveCombi(RightKouhoCnt, pN - pK);
            return 0;
        }
        if (HasLeftSpace && HasRightSpace == false) {
            if (LeftNeedCnt <= LeftKouhoCnt) return DeriveCombi(LeftKouhoCnt, pK - 2);
            return 0;
        }
        
        //Iの左区間でも、Jの右区間でも使える文字の数の、左区間での使用数で場合分け
        long TotalCnt = 0;
        int CommonCnt = pChar2 - pChar1 - 1;
        for (int L = 0; L <= Math.Min(CommonCnt, LeftNeedCnt); L++) {
            //Iの左区間の場合の数
            int RestLeftKouhoCnt = 'Z' - pChar2;
            int RestLeftNeedCnt = LeftNeedCnt - L;
            if (L < LeftNeedCnt && RestLeftKouhoCnt < RestLeftNeedCnt) continue;
            long LeftPatternCnt = DeriveCombi(RestLeftKouhoCnt, RestLeftNeedCnt);

            //Jの右区間の場合の数
            int wkRightKouhoCnt = RightKouhoCnt - L;
            if (wkRightKouhoCnt < RightNeedCnt) continue;
            long RightPatternCnt = DeriveCombi(wkRightKouhoCnt, RightNeedCnt);

            long wkCnt = DeriveCombi(CommonCnt, L) * LeftPatternCnt * RightPatternCnt;
            TotalCnt += wkCnt;
        }
        return TotalCnt;
    }

    //nCrを求める
    static long DeriveCombi(int pN, int pR)
    {
        long WillReturn = 1;
        pR = Math.Min(pR, pN - pR);

        for (int I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
        }
        for (int I = 2; I <= pR; I++) {
            WillReturn /= I;
        }
        return WillReturn;
    }
}

実行結果

省略
pN(15)=253047192320
pN(16)=348019565465
pN(17)=409484775700
pN(18)=409511334375
pN(19)=344863490400
pN(20)=241408817650
pN(21)=137949211400
pN(22)=62704500950
pN(23)=21810318400
pN(24)=5452587075
pN(25)=872414556
pN(26)=67108837
解は409511334375

解説

単調増加になった時の文字のペアと座標の組み合わせごとに、
場合の数を求めてます。