POH! Lite Perl模範解答

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

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

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

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

$M = <STDIN>;
$N = <STDIN>;

$min_cost = 0;
@q = ();
@r = ();

$min_cost = 0;
for($i = 0; $i < $N; $i++) {
    $tmp = <STDIN>;
    @tmp = split(/ /, $tmp);
    push(@q, @tmp[0]);
    push(@r, @tmp[1]);
    $min_cost += @r[$i];
}

%dp = ();
$dp_ref = {};
%dp = (%hash, 0 => 0);
for($i = 0; $i < $N; $i++) {
    %dp_tmp = %dp;

}

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

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

use List::Util qw(max);
$M = <STDIN>;
$N = <STDIN>;
@Ql = ();
@Rl = ();
$SUM_Q = 0;
$SUM_R = 0;
for($i = 0; $i < $N; $i++) {
    $tmp = <STDIN>;
    @tmp = split(/ /, $tmp);
    push(@Ql, @tmp[0]);
    push(@Rl, @tmp[1]);
    $SUM_Q += @tmp[0];
    $SUM_R += @tmp[1];
}

$m = $SUM_Q - $M;
@dp = (0)x($m+1);

for($i = 0; $i < $N; $i++) {
    $q = @Ql[$i]; $r = @Rl[$i];
    for($j = $m; $j >= $q; $j--) {
        @dp[$j] = max(@dp[$j], @dp[$j-$q]+$r);
    }
}
print($SUM_R - @dp[$m]);

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

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

$M = <STDIN>;
$N = <STDIN>;
@Ql = ();
@Rl = ();
for($i = 0; $i < $N; $i++) {
    $tmp = <STDIN>;
    @tmp = split(/ /, $tmp);
    push(@Ql, @tmp[0]);
    push(@Rl, @tmp[1]);
}



@use_list = ();
$format = '%0'.int($N).'b';
for($i = 0; $i <= 2**$N; $i++) {
    $tmp = sprintf($format, $i);
    @tmp = split(//, $tmp);
    push(@use_list, [@tmp]);
}

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

print($ans."\n");
ページの先頭へ戻る