Q54 素数で作る天秤ばかり

JavaScriptのソース

var gSosuuSet;

Solve(10,2); //    4
Solve(50,5); //66588

function Solve(pM,pN)
{
    Eratosthenes(pM);

    //場合の数[左側,右側] なDP表
    var PrevDP = new Object();
    PrevDP['0,0'] = 1;

    for(var I = 0 ; I <= gSosuuSet.length - 1 ; I++){
        var CurrDP = new Object();
        for(var EachProp in PrevDP)
            CurrDP[EachProp] = PrevDP[EachProp];

        for(var EachProp in PrevDP){
            var wkArr = EachProp.split(',');

            var NumLeft  = Number(wkArr[0]);
            var NumRight = Number(wkArr[1]);

            var NewKey1 = String(NumLeft + gSosuuSet[I]) + ',' + String(NumRight);
            var NewKey2 = String(NumLeft) + ',' + String(NumRight + gSosuuSet[I]);

            if(NewKey1 in CurrDP) CurrDP[NewKey1] += PrevDP[EachProp];
            else CurrDP[NewKey1] = PrevDP[EachProp];

            if(NewKey2 in CurrDP) CurrDP[NewKey2] += PrevDP[EachProp];
            else CurrDP[NewKey2] = PrevDP[EachProp];
        }
        PrevDP = CurrDP;
    }
    
    var Answer = 0;
    for(var EachProp in PrevDP){
        var wkArr = EachProp.split(',');
        var NumLeft  = Number(wkArr[0]);
        var NumRight = Number(wkArr[1]);
        if(NumLeft + pN == NumRight){
            Answer += PrevDP[EachProp];
        }
    }

    document.write('解は' , Answer , '<br>');
}

//エラトステネスの篩
function Eratosthenes(pN)
{
    var IsSosuuArr = new Array(pN + 1).fill(true);

    for(var I = 2 ; I <= pN ; I++){
        if (I != 2 && I % 2 == 0) continue;

        if (IsSosuuArr[I]) {
            for (var J = I * 2; J <= pN; J += I) {
                IsSosuuArr[J] = false;
            }
        }
    }

    gSosuuSet = new Array();
    for (var I = 2; I <= IsSosuuArr.length - 1; I++)
        if (IsSosuuArr[I]) gSosuuSet.push(I);
}

実行結果

解は4
解は66588

解説

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