【AtCoder版！蟻本】AOJ 0529 Darts【準備編】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210317155919p:plain
AtCoder版！蟻本の準備編で類題としてあげられているAOJ0529をPythonで解いていきます。
この解答例は制限時間オーバーしてしまいますが参考のため記事にしました。

リンク

AOJ 0529 Darts

問題文

あなたは以下のルールでダーツゲームをすることになった.

あなたは,矢を的(まと)に向かって 4 本まで投げることができる.必ずしも 4 本全てを投げる必要はなく,1 本も投げなくてもかまわない.的は N 個の部分に区切られていて,各々の部分に点数 P1,..., PN が書かれている.矢が刺さった場所の点数の合計 S があなたの得点の基礎となる.S があらかじめ決められたある点数 M 以下の場合は S がそのままあなたの得点となる.しかし,S が M を超えた場合はあなたの得点は 0 点となる.

的に書かれている点数と M の値が与えられたとき,あなたが得ることのできる点数の最大値を求めるプログラムを作成せよ.

解答例

import bisect

while True:
    n, m = map(int,input().split())
    if n == 0 and m == 0:   # 終了条件
        break
    # 的の点数
    P = []
    for i in range(n):
        P.append(int(input()))
    
    # 投げない選択肢を足す
    P.append(0)
    
    # 2投で取り得る点数
    S = []
    for i in range(n + 1):
        for j in range(i,n + 1):
            S.append(P[i] + P[j])
    
    # 二分探索のためソート
    S.sort()
    # Sの要素のうちm以下の最大値の位置+1
    num = bisect.bisect_left(S,m)
    # m以上のSの要素を除外
    if num < len(S):
        if S[num] == m:
            print(m)
            continue
        S = S[:num]

    # 取り得る最大の得点
    res = 0

    # 最大の得点を探索
    for i in range(len(S)):
        tmp = bisect.bisect_left(S,m - S[i])
        res = max(res,S[i] + S[tmp-1])
        if res == m:
            break
    print(res)

解説

4投まで行うことのできるダーツで、最大何点とることができるか答える問題です。

4重ループでは完全に間に合わなくなるので、2投で取り得る点数をリストSに入れていく半分全列挙を用いました。
計算量を減らすためリストSの要素のうちmより大きい値は除外しておきます。（結果的に間に合いませんでしたが (^_^;)

最後に最大の得点を探索です。
2投した得点をきめたあと、mに最も近くなるようなSの値を二分探索で求めます。
合計得点をresと比較して、大きければresを更新していく方針です。

残念ながらこの方法は制限時間オーバーでしたが、半分全列挙・二分探索を使用した例として記事に残します。

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

リンク