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