hitoare日記

たまに書きます

2020-03-22から1日間の記事一覧

F - Knapsack for All Segments (AtCoder Beginner Contest 159)

問題リンク atcoder.jp 問題概要 長さNの数列\(A_1,,,A_N\)が与えられる。 \(1 \leqq L \leqq R \leqq N\)に対し、\(f(L,R)\)を\(A_L\)から\(A_R\)までの数を使って和をSにする組み合わせの総数とする。 \(f(L,R)\)の総和を求めよ。 解法 各組み合わせに対し…

E - Dividing Chocolate (AtCoder Beginner Contest 159)

問題リンク atcoder.jp 問題概要 縦H、横Wマスのチョコレートがあり、一部のマスはホワイトチョコレートである。 このチョコを縦または横に一直線に切ることを何回か繰り返して、各部分に含まれるチョコレートがK個以下になるようにしたい。 切る回数の最小…