Pythonで解いたっpaizaのキャンペーン対象問題（Aランク「お菓子の詰め合わせ」）

こんなメールがpaiza運営から来ていました。

ということで、お菓子の詰め合わせを解説します。解説するコード的にも初心者に分かりやすいかなと。

提出したコードの解説

A034.py

# coding: utf-8
def main():
    import itertools
    n,yen = map(int,input().split())
    a = [int(input()) for _ in range(n)]
    s = yen
    c = n
    z = []
    for q in range(n+1,0,-1):
        for i in itertools.combinations(a,q):
            z.append(i)
    for i in z:
        if not c == len(i):
            if s == yen:
                c = len(i)
            else:
                break
        x = yen - sum(i)
        if 0 <= x and x < s:
            s = x
    print(s)
main()

このコードは提出したコードそのものです。
では解説していきましょう。

まずは変数などを初期化していきます。

    import itertools
    n,yen = map(int,input().split())
    a = [int(input()) for _ in range(n)]
    s = yen
    c = n
    z = []

変数n、変数yen、変数aは与えられた数値を入力します。
変数sと変数cはフラグの代わりに使います。
配列zはcombinationsで作った配列を格納するために初期化しています。
itertoolsは後でcombinationsを使うので呼び出しておきます。
なお、itertoolsの簡単な使い方は下の記事を読むといいでしょう。結構便利ですよ。

    for q in range(n+1,0,-1):
        for i in itertools.combinations(a,q):
            z.append(i)

これだけだと分かりずらいと思うので、例えば[1,2,3]という配列があったとしましょう。

import itertools
a = [1,2,3]
z = []
for i in range(len(a),0,-1):
    for j in itertools.combinations(a,i):
        z.append(j)
print(z)

[(1, 2, 3), (1, 2), (1, 3), (2, 3), (1,), (2,), (3,)]

このように問題の条件である「同じお菓子は複数買わない」を達成する重複のない順列が作られます。
また、問題の条件に「種類の数を最大にする」があるため、数の合計が少ない順から見ていくのではなく、数が多い順にみていくという形がやりやすくお勧めです。

次に「お菓子の総額を指定範囲内」の条件を満たすためのコードを書きます。

    for i in z:
        if not c == len(i):
            if s == yen:
                c = len(i)
            else:
                break
        x = yen - sum(i)
        if 0 <= x and x < s:
            s = x

配列zを回していきます。

        if not c == len(i):
            if s == yen:
                c = len(i)
            else:
                break

このif文は問題の条件である「お釣りを最小にすることよりも種類の数を最大にすることを優先する」を達成するために必要となります。
まず、cは最初に入力した配列の長さ（変数n）が格納されています。for文の変数であるiの長さが一致しなくなった場合、if文の中に入ります。
そこで、変数sに格納されている数値が変数yenと同じであれば、cにlen(i)の値を格納します。ただし、数値が違うとなれば「数値が違うということはすべての条件を満たす値が出た」ということでfor文から抜け出します。

        x = yen - sum(i)
        if 0 <= x and x < s:
            s = x

変数xにyen - sum(i)を格納します。この数値は変数yenのおつりが最小かを次に見るために使います。
if 0 <= x and x < sでは、0 <= xはxが0よりも大きいかを見ています。所持金300円では合計400円の商品は買えないでしょうから。x < sはおつりの数がsよりも小さいかを見ています。問題の条件である「お釣りを最小」を達成するために必要です。
この条件に合致するのであれば、sにxを格納します。
以降、変数sが変数yenと違う数値になるまで回します。

    print(s)

どのくらいかを判別できたら表示します。
これで終了です。

実行速度を早くする

ただ、先ほどのコードは最後のチェックで0.5秒以上かかるという問題があります。
ということで、実行速度を既存のコードをほとんど変えずに早くしましょう。ある意味、効率的な最適化を考えるきっかけにもなる問題でしょう。

なお、他の高速化はこの記事が書いてくれています。

def main():
    # ここに入れるよ。
main()

そもそも全部見る必要はありません。問題にお菓子の総額を指定範囲内という条件があるので、指定金額を越えたものは切り捨てましょう。

    for q in range(n+1,0,-1):
        for i in combinations(a,q):
            if sum(i) <= yen:
                z.append(i)

これだけで使う時間が半分になります。
おや、配列を作るくらいならこの時点で適合するか見たほうがいいのではないでしょうか。

    for i in z:
        if not c == len(i):
            if s == yen:
                c = len(i)
            else:
                break
        x = yen - sum(i)
        if 0 <= x and x < s:
            s = x

このコードを改変してz.append(i)の部分に入れます。

    for q in range(n+1,0,-1):
        for i in combinations(a,q):
            if sum(i) <= yen:
                x = yen - sum(i)
                if 0 <= x and x < s:
                    s = x
        if s != yen:
            break

これで与えられる値によっては0.05秒くらいなら早くなります。また、このようにすることで、コード的にも読みやすくなったのではないでしょうか。プログラムの最適化とは、まさにコードを読みやすくするという利点もついてくるお得パックともいえるでしょう。

このコードの最終的な形はこうなりました。

# coding: utf-8
def main():
    from itertools import combinations
    n,yen = map(int,input().split())
    a = [int(input()) for _ in range(n)]
    s = yen
    for q in range(n+1,0,-1):
        for i in combinations(a,q):
            if sum(i) <= yen:
                x = yen - sum(i)
                if 0 <= x and x < s:
                    s = x
        if s != yen:
            break
    print(s)
main()

感想

これより早くしたいのであればPythonではなくC言語とかを使ったほうがいいですね。それから配列を作らなくてもいいかな、フラグを使ったりして判別できるようにしようか。
他の問題も解いていきたいですね。