問題 atcoder.jp 問題概要 N問の問題があるコンテストがあり、i問目(1-index)の問題の配点は p[i-1]点である。この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。 解法 dp[i][j] : i番目まで見て…

問題 atcoder.jp 問題概要 N段の直角三角形状の数列が与えられる。 例) 7 2 3 1 5 4 頂点からスタートして真下もしくは右下に行くことが出来る。底辺までたどり着いたときに経路中の数値の合計の最大値を求めよ。 上の例だと7+3+5=15 解法 上からi番目、左か…

問題 atcoder.jp 問題概要 N枚のカードがあり、i番目(1-index)のカードには整数x[i-1]が書かれている。 何枚かカードを選びカードの整数の平均がAとなるようにしたい。そのような選び方は何通りあるか。 解法 平均を平均のまま扱うのは大変なので合計と個数…

問題 atcoder.jp 問題概要 コインがN枚あり、i番目(1-index)のコインの表が出る確率がp[i-1]、裏が出る確率が1-p[i-1]である。 N枚のコインを投げたとき、表の個数が裏の個数を上回る確率を求めよ。 解法 dp[i][j] : i番目(1-index)のコインまで投げたときに…

問題 atcoder.jp 問題概要 薬品がN個あり、i個目の薬品はタイプAの薬品をa[i-1]グラム、タイプBの薬品をb[i-1]グラム含み、価格はc[i-1]である。 これらの薬品のうちからいくつか選んで混合し、タイプAとタイプBの薬品の混合比がMa:Mbとなるようにしたときの…

問題 atcoder.jp 問題概要 ナップサック問題に言い換える。品物がN個ありi番目(1-index)の重さはA[i-1]、価値はB[i-1]である。 重さがWを超えず、個数がKを超えないように選ぶとき、価値の合計の最大値を求めよ。 解法 個数制限がない場合は普通のナップサッ…