こちらでは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"); }