hitoare日記

たまに書きます

2020-05-31から1日間の記事一覧

E - Count Median(AtCoder Beginner Contest 169)

問題リンク atcoder.jp 問題概要 長さ\(N\)の整数列\(A_i\)と\(B_i\)が与えられていて、\(A_i \leqq B_i\)が成り立つ。 各iに対して\(A_i \leqq X_i \leqq B_i\)となる整数\(X_i\)をとった時、\({X_i}\)の中央値として有り得る値はいくつあるか。 解法 まず\…

F - Knapsack for All Subsets(AtCoder Beginner Contest 169)

問題リンク atcoder.jp 問題概要 省略 解法 Knapsack for All Segmentsの類題。 \(dp[i][j] =\) {\(A_1,...,A_i\)の各部分集合に対する、和がjとなる部分集合の数} と置いてDPする。 遷移は \(dp[i+1][j] = 2dp[i][j] + dp[i][j-A_{i+1}]\) となる。 右辺の…