Q61 互い違いに並べ替え

JavaScriptのソース

Solve( 4);
Solve(20);

function Solve(pN)
{
    const UB = pN - 1;

    //場合の数[左のマス数][右のマス数]なDP表
    var PrevDP = DeriveDPArr(UB);

    //初期配置のループ
    for(var I = 0 ; I <= UB ; I++){
        PrevDP[I][UB - I] = 1;
    }
    //document.write("初期配置<br>");
    //DebugPrint(PrevDP,UB);

    for(var I = 2 ; I <= pN ; I++){
        var CurrDP = DeriveDPArr(UB);

        for(var J = 0 ; J <= UB ; J++){
            for(var K = 0 ; K <= UB ; K++){
                if(PrevDP[J][K] == 0) continue;

                //右に移動する場合
                if(I%2 == 1){
                    for(var L = 0 ; L <= K - 1 ; L++){
                        var NewJ = J + L;
                        var NewK = K - 1 - L;
                        CurrDP[NewJ][NewK] += PrevDP[J][K];
                    }
                }

                //左に移動する場合
                else{
                    for(var L = 0 ; L <= J - 1 ; L++){
                        var NewJ = J - 1 - L;
                        var NewK = K + L;
                        CurrDP[NewJ][NewK] += PrevDP[J][K];
                    }
                }
            }
        }
        //document.write(I , "でのDP結果<br>");
        //DebugPrint(CurrDP,UB);
        PrevDP = CurrDP;
    }
    document.write('N=' , pN , 'だと' , PrevDP[0][0] * 2, '通り<br>');
}

function DeriveDPArr(pUB)
{
    var DPArr = new Array(pUB + 1);
    for(var I = 0 ; I <= pUB ; I++){
        DPArr[I] = new Array(pUB + 1);
        DPArr[I].fill(0);
    }
    return DPArr;
}

//DPのデバッグ用
function DebugPrint(pArr,pUB)
{
    for(var I = 0 ; I <= pUB ; I++){
        for(var J = 0 ; J <= pUB ; J++){
            document.write("pArr[" , I , "][" , J , "]=" , pArr[I][J] , "   ");
        }
        document.write("<br>");
    }
}

実行結果

N=4だと10通り
N=20だと740742376475050通り

解説

動的計画法で解いてます。