POH! Lite JavaScript模範解答

こちらではpaiza事務局側で作成した模範解答を掲載しています。

JavaScript: paiza事務局作成コード Vol.3 解説ブログ版

解説ブログ: もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら

得点:100点
通過テストケース:7/7

var input = [];
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  input.push(line);
});

reader.on('close', () => {
  main();
});

function main() {
    M = Number(input[0]);
    N = Number(input[1]);
    q = [];
    r = [];
    min_cost = 0;

    for(i = 0; i < N; i++) {
        tmp = input[2+i].split(' ');
        q[i] = Number(tmp[0]);
        r[i] = Number(tmp[1]);
        min_cost += r[i];
    }

    dp = new Array();
    dp[0] = 0;
    for(i = 0; i < N; i++) {
        dp_tmp = dp.concat();
        for(key in dp) {
            total_q = Number(key) + q[i];
            total_r = dp[key] + r[i];
            if( (total_q in dp_tmp) == false) {
                dp_tmp[total_q] = total_r;
            } else {
                if(dp_tmp[total_q] > total_r) {
                    dp_tmp[total_q] = total_r;
                }
            }

            if(total_q >= M && min_cost > total_r) {
                min_cost = total_r
            }
        }
        dp = dp_tmp;
    }

    console.log(min_cost + "\n");
}

JavaScript: paiza事務局作成コード Vol.2 動的計画法

得点:100点
通過テストケース:7/7

var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
    input += chunk;
});
process.stdin.on('end', function(){
    input = input.split('\n');
    main();
});

function main() {
    M = Number(input[0]);
    N = Number(input[1]);
    QR = [];
    SUM_Q = 0;
    SUM_R = 0;
    for(i = 0; i < N; i++) {
        tmp = input[2+i].split(' ');
        q = Number(tmp[0]);
        r = Number(tmp[1]);
        SUM_Q += q;
        SUM_R += r;
        QR.push([q, r]);
    }

    DP_M = SUM_Q - M;
    dp = new Array(DP_M+1);
    for(i = 0; i < DP_M+1; i++)dp[i]=0;

    for(i = 0; i < N; i++) {
        q = QR[i][0];
        r = QR[i][1];
        for(j = DP_M; j >= q; j--) {
            dp[j] = Math.max(dp[j], dp[j-q]+r);
        }
    }

    console.log(SUM_R - dp[DP_M] + "\n");
}

JavaScript: paiza事務局作成コード Vol.1 O(2^n)

得点:71点
通過テストケース:5/7

var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
    input += chunk;
});
process.stdin.on('end', function(){
    input = input.split('\n');
    main()
});

function main() {
    M = Number(input[0]);
    N = Number(input[1]);
    QR = [];
    for(i = 0; i < N; i++) {
        tmp = input[2+i].split(' ');
        q = Number(tmp[0]);
        r = Number(tmp[1]);
        QR.push([q, r]);
    }

    //m社のうちi番目の会社を使うか使わないかの表を作る
    //3社とかなら
    // A, B, C
    // 1, 1, 1
    // 1, 1, 0
    // 1, 0, 1
    //.....続く...
    //みたいな1を使う0は使わないの表を作る

    use_list = []
    pad = "";
    for(i = 0; i < N; i++)pad += "0"
    for(i = 0; i < Math.pow(2, N); i++){
        tmp = (pad+i.toString(2)).slice(N*-1);
        tmp_list = [];
        for(j = 0; j < tmp.length; j++) {
            tmp_list.push(tmp[j]);
        }
        use_list.push(tmp_list);
    }

    //使う使わないリストから、人月を満たせる組み合わせで最安を探す
    ans = 0;
    for(i = 0; i < N; i++)ans += QR[i][1];
    for(i = 0; i < use_list.length; i++) {
        cost = 0;
        ningetsu = 0;
        for(j = 0; j < N; j++) {
            if(use_list[i][j] == '1') {
                ningetsu += QR[j][0];
                cost += QR[j][1];
            }
        }
        if(ningetsu >= M && ans > cost) {
            ans = cost;
        }
    }

    console.log(ans + "\n");
}
ページの先頭へ戻る