問題リンク atcoder.jp 問題概要 数直線上に\(N\)体のモンスターがいる。それぞれのモンスターは座標\(X_i\)にいて、体力は\(H_i\)である。 次の操作を好きなだけおこなう。 好きな座標\(x\)を選び、爆弾を使用する。このとき座標が\(x-D\)以上\(x+D\)以下の…

問題リンク atcoder.jp 問題概要 \(N\)個の正整数\(A_1,…A_N\)が与えられる。 正整数列\(B_1,…B_N\)であって、\(A_iB_i = A_jB_j\) が全ての\( (i,j)(1\leqq i < j\leqq N)\)にして成り立つ物のうち、\(B_1+B_2+ \ldots +B_N\)の最小値を\(10^9+7\)で割った…

問題リンク atcoder.jp 問題概要 \(N\)頂点の木が与えられる。\(N-1\)本の辺を白または黒に塗り分ける方法であって、次の\(M\)個の条件全てを満たすものはいくつあるか。 条件\(i(1≦i≦M) \) : \(u_i\)と\(v_i\)を結ぶパスの間に、黒い辺が少なくとも1つ存在…

問題リンク atcoder.jp 問題概要 N頂点M辺の無向グラフが与えられる。各頂点を白または黒に塗り分け、更に辺に重みを割り当てる方法であって次の条件を満たすものは存在するか。存在すれば1つ構築せよ。 \(1\leqq i\leqq N\)にし、点iから色の異なる点に移動…

公式解説と解法が違っていたので。 問題リンク atcoder.jp 問題概要 長いので省略 解法 Cが小さいものからとる方が良いので、まずCを小さい順にソートする。 動的計画法によって答えを求める。 dp[i] = (i文字目まで見た時のfの総和)とする。 1文字の文字列…