【AtCoder版！蟻本】ARC029 A - 高橋君とお肉【bit全探索】

AtCoder版！蟻本のbit全探索で類題としてあげられているARC029 A - 高橋君とお肉をPythonで解いていきます。

リンク

atcoder.jp

AtCoder Regular Contest 029 A - 高橋君とお肉

問題文

高橋君は友達とキャンプに行くことになった。
高橋君と友達は性能が同じである 2 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。
2 つの肉焼き器にまたがって 1 つのお肉を置くことはできない。また、お肉は全部で N 個あり、お肉には 1 から N まで番号が付けられている。お肉 i を焼くのには、どちらの肉焼き器でも時間 ti だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。

高橋君はお肉を焼く係であり、N 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。
すべてのお肉を焼くのにかかる時間の最小値を求めよ。

制約

・N(1≦N≦4)
・ti(1≦ti≦50)

解答例

# bit全探索

n = int(input())

T = []
for i in range(n):
    T.append(int(input()))

ans = 1e5
for bit in range(2**n):
    time1 = 0 # 肉焼き器1号で焼き終わる時間
    time2 = 0 # 肉焼き器2号で焼き終わる時間
    for i in range(n):
        if (bit >> i) & 1: # bitが1なら1号で焼く
            time1 += T[i]
        else:
            time2 += T[i]
    tmp = max(time1,time2)
    ans = min(ans,tmp)

print(ans)

解説

2つの肉焼き器を使ってすべての肉を最も早く焼くのにかかる時間を答える問題です。

この問題もbit全探索をもちいて、bitが1の場合は肉焼き器1号で 0のときは2号で焼くことを想定しています。
各肉焼き器で必要な時間は、その機械で焼く肉の焼き上がり時間を足し合わせたものなので、1号はtime、2号はtime2にそれぞれ足し合わせました。

time1とtime2の大きいほうが その振り分けの焼き上がり終える時間になるので、ans変数と比較して小さければ その値を代入します。

ループを抜けたあとにans変数を出力すればACです！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク