Q35 かしこい幹事の集金術

JavaScriptのソース

Solve( 5);
Solve(32);

function Solve(pNinzuu)
{
    var Answer = 0;
    for(var I = 0 ; I <= pNinzuu ; I++){
        Answer += ExecDP(I , pNinzuu - I);
    }
    document.write(pNinzuu , '人だと' , Answer , '通り<br>');
}

//動的計画法で場合の数を求める
function ExecDP(pM , pN)
{
    const UB = pM;

    //場合の数[1000円札で払った人の数]なDP表
    var PrevDP = new Array(UB + 1).fill(0);
    PrevDP[0] = 1;

    for(var I = 1 ; I <= pM + pN ; I++){
        var CurrDP = new Array(UB + 1).fill(0);
        for(var J = 0 ; J <= UB ; J++){
            if(PrevDP[J] == 0) continue;

            //1000円札で払う場合
            var NewJ = J + 1;
            if(NewJ <= pM){
                CurrDP[NewJ] += PrevDP[J];
            }

            //5000円札で払う場合
            var Pay5000 = I - J;
            if(Pay5000 <= pN){
                var RestMaisuu = J * 3 - (I - J) * 2;
                if(RestMaisuu >= 0){
                    CurrDP[J] += PrevDP[J];
                }
            }
        }
        PrevDP = CurrDP;
    }
    //document.write('M=' , pM , 'N=' , pN , 'だと' , PrevDP[UB] , '通り<br>');
    return PrevDP[UB];
}

実行結果

5人だと12通り
32人だと1143455572通り

解説

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