問題 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を超えないように選ぶとき、価値の合計の最大値を求めよ。 解法 個数制限がない場合は普通のナップサッ…

問題 atcoder.jp 問題概要 N個の品物があり、i番目(1-index)の品物の品物の重さはw[i-1]で、価値はv[i-1]である。 品物を重さの合計がWを超えないように選ぶとき価値の総和の最大値を求めよ。 解法 ナップサックDPである。dp[i][j] : i番目まで見て重さの合…

ソート済みのvector Aに対してhoge以上の最小の要素のイテレータ lower_bound(A.begin(), A.end(), hoge)hogeを超える最小の要素のイテレータ upper_bound(A.begin(), A.end(),hoge) 値がhoge以上の要素の個数 A.end() - lower_bound(A.begin(), A.end(), ho…

二次元累積和とは このような配列を考える。これを配列Aとする。配列Aの中の任意の長方形の区間の総和を求めたいとする。 例 図の水色のマスの合計は、1+5+2+6+3+9+3+8=37である。 これは、A[1][2]からA[2][5]までの総和といえる。 これをΣ([1][2],[2][5])と…

グリッド グリッド上のBFS(最短経路) //各点のスタートからの距離を配列で返す //si,sj:スタートの座標 //スタートは壁ではない //辿り着けない:-1 vector<vector<int>>bfs_grid_pass(int si,int sj, vector<vector<char>>field) { vector<int>di; di = { 0,1,0,-1 }; vector<int>dj; dj = { 1,0</int></int></vector<char></vector<int>…