問題 解法 解答 問題 atcoder.jp 解法 v を降順にソートし，前から A ~ B 個を平均値が小さくならない間通り数を求め，その合計を答えにする．前から i 個取った時の通り数は C( (v の中にある v[i] の個数), (今まで取った中にある v[i] の個数) ) になる．…

問題 解法 解答 問題 atcoder.jp 解法 「dp(i, j, k) := 薬品 i まででタイプ A を j タイプ B を k 集めるときの最小コスト」で DP をする．O(N^3)． 解答 atcoder.jp

問題 解法 解答 問題 atcoder.jp 解法 N <= 100 と小さいので，ワーシャルフロイド法を用いて全頂点間の最短コストを更新していく．もし，dist[i][j] > dist[i][k] + dist[k][j] であるならば，辺 (i -> j) はどの最短経路にも含まれない．これを数えていき…