Pythonのタイムアウトについて

Question

#Pythonで問題を解いているのですがTimed Outと出てしまい、どうしていいか分かりません。
（問題）
We want make a package of goal kilos of chocolate. We have small bars (1 kilo each) and big bars (5 kilos each). Return the number of small bars to use, assuming we always use big bars before small bars. Return -1 if it can't be done.
チョコレートのパック（goal）を作りたい。1kgの小さいチョコバーと5kgの大きいチョコバーがある。小さいチョコバーはいくつ必要かを返しなさい。（最初に大きいチョコバーを用いてください）また、作れない場合は-1を返してください。make_chocolate(small,big,goal)
smallには1kgのチョコバーの数、bigには5kgのチョコバーの数、goalには目標のkgを渡します。
make_chocolate(4, 1, 9) → 4
make_chocolate(4, 1, 10) → -1
make_chocolate(4, 1, 7) → 2
自分のコードはいかになります。

def make_chocolate(small, big, goal):
    if goal>small+big*5:
        return -1
    if goal<5:
        count=0
        for i in range(1,small+1):
            zero=goal-1
            count+=1
            if zero==0:
                return count
        if zero!=0:
            return -1
    else:
        target=goal
        amount=big
        for i in range(big):
            target=goal-5
            amount-=1
            if target>=5 and amount!=0:
                continue
            if target<5:
                break
            if amount==0:
                break
        if target<=small:
            return target
        else:
            return -1

Pycharmで確認したところしっかりと値を返しているのですがどのように実行時間を縮めるのでしょうか？方法を教えて頂けると大変助かります。

Comments

[jeanbiego]

引数にsmall, big, goalとありますが、それぞれどのような意図の変数なのか説明を書いてください。

Answer 1

主さんの回答はO(N)なのでtime outになったのかもしれませんね。
以下僕ならこう書きます。これ以上簡単にならないと思います。O(1)

def make_chocolate(small, big, goal):
    remains = goal - min(big, goal // 5) * 5
    if remains <= small:
        return remains
    return -1


assert make_chocolate(4, 1, 9) == 4
assert make_chocolate(4, 1, 10) == -1
assert make_chocolate(4, 1, 7) == 2

Comments

[Charowan]

ありがとうございます。私は初心者なのでわからないことが多いのですが、O(N)とはなんでしょうか？
またどのようにしたらそのような短くてかつ正確なコードを書くことができるのでしょうか？練習を重ねていくうちにできるようになるのでしょうか？
質問が多くてすいません。

[退会済みユーザー]

Oはランダウのオーと呼ばれるもので、ソフトウェアの世界では計算の複雑さを表します。Oは計算時間(time complexity)とメモリの使用(space complexity)それぞれについて考えないといけないのですが、何も言わなければ一般に計算時間のことです。ざっくり言って入力した値NについてforループがあればO(N)です。二重のforループがあればO(N^2)となって計算は爆発的に増えます。

コードの書き方は逐次的な書き方をなるべく避けることを心がけています。例えばforループやif/elseが避けられないかを考え、専用の関数があればそれを使います。今回ならmin(a, b)を使うことでif文が一つ減りました。関数型言語やSQLのような宣言的な書き方しか許さない言語もありますが、そこまで厳しくやるわけではなくざっくりとした方針です。

[Charowan]

そうなんですね。そしたら以前私が競技プログラミングなどで提出したものが実行時間超過になるのはforループをたくさん使ってたからなんですね！
分かりました。
丁寧な回答ありがとうございます。感謝しています！！

Answer 2

• 引数にbigとsmallを与えるのは、そうしないと行けない理由が問題文（の書かれてないところ）にあるのですか？

→あ、Kenjiさんの回答みてわかりました。手持ちのsmallとbigの個数でgoalが作れるかという問題だったんですね。だとすると私のコードは間違ってますね。
~~そのへんがよくわかりませんが、簡単に書くと下のようになるかと思います。
~~

def make_chocolate(goal):
    big_wt = 5
    if goal < big_wt:
        return -1
    return goal % big_wt  # goalをbigのweight(5kg)で割った余り=small(1kg)の個数
print(make_chocolate(9))
# 4
print(make_chocolate(10))
# 0
print(make_chocolate(7))
# 2

Comments

[Charowan]

問題で引数は必ず(small, big, goal)でなければなりません。３つの引数を渡してsmallの個数とbigの個数でgoal(kg)が作れるかという問題です。説明不足ですいません。