[python]パラメトリック調査

最適化の問題
特定の条件を満たす変数の最大値または最小値を探す問題

実際,最適化問題の概念はこれよりずっと複雑である.

しかし,パラメトリック測定を理解するためには,上記の定義を十分に理解できる.

ex.全員に同じ数のビーズを割り当てる場合、可能なビーズの数の最大値は?

けっていもんだい
計算問題では「Yes」または「No」で結果の質問に答えることができます

ex.101は少数ですか?

ex.グラフィックのノードAからノードBへのパスは存在しますか?

パラメトリックメジャー
最適化問題を決定問題に変換する方法
パラメトリック測定を適用できる問題

1または0の関数f(i)があります.

f(i) = 0 i未満のすべてのjのうちf(j) = 0である場合

f(i) = 1人iの最小値、f(i) = 0人iの最大値を求める.

最適化問題=>意思決定問題

f(i) = 1이 되는 i의 최소값을 구하여라 => f(i) = 1인가?

上の数学の説明はあまり適切ではありませんが、実は理解すれば難しくありません.例を通して理解する.友達の誕生日プレゼントを買うAさんは自分が買える一番高いプレゼントを買いたいです.そのため、まずショッピングモールで販売されている商品を価格順に並べ替えます.

そして二分探索アルゴリズムを用いて,買える最も高い贈り物の価格を探索する.
両端をそれぞれ左、右の後ろに置き、毎回左、右の中間を中央に置き、中間貨物の価格を支払い可能な価格と比較する.
以下はAが出す価格が1600ウォンの時、Aが買える最も高いプレゼントを探す過程だ.

上の写真を見ると、この探索とは少し違います.

1600元の価格の物品を探す二分探索であれば、1行目は1100 < 1600であるため、leftは1100の次のインデックスとして探索を続ける.1100ウォンの価値があるものは探しているものではないからだ.

逆に、上に左を真ん中に置いて探索を続けます.1100ウォンの価値のあるものは、やはり探したいもの、つまり買える最も高いものかもしれないからだ.さらに,これはすぐに二分探索とパラメータ研究の違いを示した.二分検索が特定の値自体を検索する場合、パラメトリック検索は、特定の条件を満たす最適な(最小または最大)値を検索します.

このように,二分探索とパラメータ研究では,条件文の異なる処理部分が誤りやすい部分であるため,注意してみる.

例の質問-木を切る(白駿2805号)
問題のソース
少なくともmメートルの木を家に持ち帰るために、カッターが設定できる高さの最値を求めます.
解決方法:左側、右側をそれぞれ0、10000000(木の最大高さ)に設定し、パラメトリック測定により木の長さがMメートルより大きいカッター設定高さの最大値を求める.

from sys import stdin


def get_tree_length(cut_height):
    """
    절단기의 높이를 cut_height로 설정했을 때 얻을 수 있는 나무의 총 길이를 구한다.
    """
    global trees
    
    return sum([(tree - cut_height) for tree in trees if tree > cut_height])


def get_max_height(target):
    """
    target미터 이상의 나무를 가져가기 위해 절단기에 설정 가능한 높이의 최댓값을 구한다.
    """
    global trees
    start, end = 0, 1000000000

    while start <= end:
        mid = (start + end) // 2

        if get_tree_length(mid) >= target:
            start = mid + 1
        else:
            end = mid - 1

    return end


N, M = map(int, stdin.readline().split())
trees = [int(x) for x in stdin.readline().split()]

print(get_max_height(M))

リファレンスソース
https://www.youtube.com/watch?v=F6lKjRDlOpk
https://www.crocus.co.kr/1000
https://sarah950716.tistory.com/16