こちらではpaiza事務局側で作成した模範解答を掲載していす。
PHP: paiza事務局作成コード Vol.3 解説ブログ版
解説ブログ: もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら
得点:100点
通過テストケース:7/7
<?php fscanf(STDIN, '%d', $M); // 必要人数 fscanf(STDIN, '%d', $N); // 入力社数 // q 各下請け会社の人員数 // r 各下請け会社のへの発注費用 $min_cost = 0; for($i = 0; $i < $N; $i++) { fscanf(STDIN, '%d %d', $q[$i], $r[$i]); $min_cost += $r[$i]; } $dp = array(); $dp[0] = 0; // $dp[人数]=最低価格 // 入力社数分ループ for($i = 0; $i < $N; $i++){ $dp_tmp = $dp; // $dp_tmpは足しあげ処理結果を格納 // 人数ループ foreach ($dp as $key => $value){ $total_q = $key + $q[$i]; // 入力済み人数に足しあげる $total_r = $value + $r[$i]; if(!isset($dp_tmp[$total_q])){ // 該当人数に値が入力されていなかった場合 $dp[$total_q] = $total_r; }else{ // 当該人数が入力済みの場合より小さい合計金額を入力 if($dp_tmp[$total_q] > $total_r){ $dp[$total_q] = $total_r; } } // if($total_q >= $M and $min_cost > $total_r){ $min_cost = $total_r; } } } print $min_cost;
PHP: paiza事務局作成コード Vol.2 動的計画法
得点:100点
通過テストケース:7/7
<?php fscanf(STDIN, '%d', $M); fscanf(STDIN, '%d', $N); $QR = array(); $sum_q = 0; $sum_r = 0; for($i = 0; $i < $N; $i++) { fscanf(STDIN, '%d %d', $QR[$i][0], $QR[$i][1]); $sum_q += $QR[$i][0]; $sum_r += $QR[$i][1]; } $m = $sum_q - $M; $dp = array(); for($i = 0; $i < $m+1; $i++)$dp[$i] = 0; for($i = 0; $i < $N; $i++) { $q = $QR[$i][0]; $r = $QR[$i][1]; for($j = $m; $j >= $q; $j--) { $dp[$j] = max($dp[$j], $dp[$j-$q]+$r); } } print(($sum_r - $dp[$m])."\n");
PHP: paiza事務局作成コード Vol.1 O(2^n)
得点:71点
通過テストケース:5/7
<?php fscanf(STDIN, '%d', $M); fscanf(STDIN, '%d', $N); $QR = array(); for($i = 0; $i < $N; $i++) { fscanf(STDIN, '%d %d', $QR[$i][0], $QR[$i][1]); } $use_list = array(); for($i = 0; $i < pow(2, $N); $i++) { $use_list[] = str_split(str_pad(decbin($i),$N,"0",STR_PAD_LEFT)); } #使う使わないリストから、人月を満たせる組み合わせで最安を探す $ans = 0; foreach($QR as $v) { $ans += $v[1]; } foreach($use_list as $v) { $cost = 0; $ningetsu = 0; foreach($v as $key => $vv) { if($vv == 1) { $ningetsu += $QR[$key][0]; $cost += $QR[$key][1]; } } if($ningetsu >= $M && $ans > $cost) { $ans = $cost; } } print($ans."\n");