POH! Lite Python模範解答

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

Python: 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;

}

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

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

#coding: utf-8

if __name__ == "__main__":
    m, n = input(), input()
    qr = []
    sum_q = 0
    sum_r = 0
    for i in xrange(n):
        q, r = map(int, raw_input().split())
        qr.append([q, r])
        sum_q += q
        sum_r += r

    dp_m = sum_q - m
    dp = [0 for i in xrange(dp_m+1)]

    for q, r in qr:
        for j in range(q, dp_m+1)[::-1]:
            dp[j] = max(dp[j], dp[j-q] + r)

    print sum_r - dp[dp_m]

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

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

#coding:utf-8
if __name__ == "__main__":
    m = input()
    n = input()
    qr = []
    for i in range(n):
        tmp = raw_input().split()
        qr.append([int(tmp[0]), int(tmp[1])])

    #m社のうちi番目の会社を使うか使わないかの表を作る
    #3社とかなら
    # A, B, C
    # 1, 1, 1
    # 1, 1, 0
    # 1, 0, 1
    #.....続く...
    #みたいな1を使う0は使わないの表を作る

    use_list = []

    #2進数で考えると
    for i in xrange(2**n):
        use_list.append(map(int, list(bin(i)[2::].zfill(n))))

    #使う使わないリストから、人月を満たせる組み合わせで最安を探す
    ans = sum([i[1] for i in qr])
    for i in use_list:
        cost = 0
        ningetsu = 0
        for j, v in enumerate(i):
            if v == 1:
                ningetsu += qr[j][0]
                cost += qr[j][1]
        if ningetsu >= m and ans > cost:
            ans = cost

    print ans
ページの先頭へ戻る