paizaオンラインハッカソン(略してpoh!)模範解答コード一覧 | ITエンジニア専門の転職サイト【paiza転職】

POH! Lite　PHP模範解答

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