Pythonのコンテストで達成可能なポイントを見つけるためのプログラム

複数の問題があるプログラミングコンテストに参加しているが、1つの問題を解決するとコンテストが終了するとします。ここで、ポイントと呼ばれる同じ長さの数の2つのリストとチャンスがあるとします。それを説明するために、ここでi番目の問題については、points[i]ポイントでそれを解決する可能性[i]パーセントの可能性があります。また、試行できる問題の数を表す別の値kがあります。同じ問題を2回試みることはできません。

最適な戦略を立てる場合、コンテストで獲得できるポイント数の期待値を見つける必要があります。これは、最も近い整数に丸められます。 i番目の問題を試行することの価値はpoints[i]*チャンス[i]/100.0として期待できます。これは、平均して得られるポイントの数を表します。

したがって、入力がpoints =[600、400、1000]、chances =[10、90、5]、k =2の場合、出力は392になります。

これを解決するには、次の手順に従います-

• n：=ポイントのサイズ

• 0からnの範囲のiの場合、実行

• チャンス[i]：=チャンス[i] / 100.0

• R：=降順で並べ替えられた0〜3を配置

• int（dp（0、K））

  を返します

• 関数dp（）を定義します。これにはi、kが必要です

  • iがnと同じ場合、

    • 0.0を返す

  • j：=R [i]

  • p：=チャンス[j]

  • ev：=p*ポイント[j]

  • kが1と同じ場合、

    • ev、dp（i + 1、k）の最大値を返す

  • dp（i + 1、k --1）*（1-p）+ ev、dp（i + 1、k）

    の最大値を返します

例

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, points, chances, K):
      n = len(points)
      for i in range(n):
         chances[i] /= 100.0
      R = sorted(range(n), key=points.__getitem__, reverse=True)
      def dp(i, k):
         if i == n:
            return 0.0
         j = R[i]
         p = chances[j]
         ev = p * points[j]
         if k == 1:
            return max(ev, dp(i + 1, k))
         return max(dp(i + 1, k - 1) * (1 - p) + ev, dp(i + 1, k))
      return int(dp(0, K))

ob = Solution()
print (ob.solve([600, 400, 1000], [10, 90, 5], 2))

入力

[600, 400, 1000], [10, 90, 5], 2

出力

392