Q53 重さが素数の荷物を運ぶエレベーター

JavaScriptのソース

var gSosuuSet;

Solve(   20,  3); //   30
Solve(10000,500); //15784

function Solve(pN,pCntLimit)
{
    Eratosthenes(pN);
    var MinWeightLimit = ExecNibunHou(pCntLimit);
    document.write('n=' , pN , 'で、運ぶ回数=' , pCntLimit ,
                   'での最小の重量制限=' , MinWeightLimit , '<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);
}

//二分法で最小の重量制限を返す
function ExecNibunHou(pCntLimit)
{
    var L = Math.max(gSosuuSet[gSosuuSet.length - 1]);
    if(CanCarry(pCntLimit,L)) return L;

    var SumVal = 0;
    for(var I = 0 ; I <= gSosuuSet.length - 1 ; I++){
        SumVal += gSosuuSet[I];
    }
    var R = SumVal;

    while (L + 1 < R) {
        var Mod = (L + R) % 2;
        var Mid = (L + R - Mod) / 2;
        if(CanCarry(pCntLimit,Mid)) R = Mid;
        else L = Mid;
    }
    return R;
}

//運ぶ回数と重量制限を引数として、運べるかを返す
function CanCarry(pCntLimit,pWeightLimit)
{
    if(pWeightLimit < Math.max(gSosuuSet)) return false;

    var CurrCnt = 0;
    var CurrWeightSum = 0;
    for(var I = 0 ; I <= gSosuuSet.length - 1 ; I++){
        if(CurrWeightSum + gSosuuSet[I] > pWeightLimit){
            CurrWeightSum = 0;
            CurrCnt++;
        }
        CurrWeightSum += gSosuuSet[I];
    }
    CurrCnt++;
    return CurrCnt <= pCntLimit;
}

実行結果

n=20で、運ぶ回数=3での最小の重量制限=30
n=10000で、運ぶ回数=500での最小の重量制限=15784

解説

二分法で解いてます。