atcoder.jp 問題概要 $ N $個の宿題があり、1日に1つずつ終わらせていく。各宿題には期限$ A_i $ が設定されており、宿題$ i $をDay $ A_i $までに終わらせると$ X_i $点、それ以後に終わらせると$ Y_i $点が得られる。$ 1\leq k \leq N $なる$ k $について…

atcoder.jp 問題概要 $ N $頂点$ M $辺のグラフ $ G $があり、頂点と辺には重みが与えられている。このグラフから辺を削除して、次の条件を満たすようにしたい。 条件：「削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その…

atcoder.jp 問題概要 $ N $頂点の木(辺は$(x_1,y_1),\dots,(x_{N-1},y_{N-1})$)の頂点を白と黒に塗り分ける。ただし、黒い頂点どうしは相互に黒い頂点のみを通って到達可能でなければならない。そのような塗り方のうち、頂点$i$が黒く塗られるものは何通りあ…

D - No Need 問題概要 枚のカードがあり，カードには正の整数が書かれている．以下の条件を満たすの個数を求めよ． 条件 カード$i$以外の$N-1$枚のカードの部分集合で，書かれている数の総和Sumが$K-a_i \leq Sum\leq K-{1}$となる部分集合は存在しない． 制…

問題 H - 三角形と格子点 三角形ABCの3頂点を A B C となるようにとる．このようにして作られる個の三角形について三角形の内部に存在する格子点の個数の総和を求めよ．(mod ) 制約 残りの制約はA,B,Cの位置関係について x_a < x_c< x_b, y_a < y_b < y_c が…

問題 B - RGB Coloring 解法 赤と青を独立に塗るだけ． note とする．まず を1つ固定し，A点をx回，B点をy回得てK点にする組み合わせを考える． 緑色に塗る個数をi個で固定すると，赤x-i個 青y-i個 緑i個 無(N-x-y+i)個の組み合わせとなるので，塗り方は 通…

agc002.contest.atcoder.jp 問題 グラフ中の辺に番号がつけられている。クエリが与えられるので、「辺のみを残した部分グラフ中で頂点集合またはから到達可能な頂点が個以上になる」ようなの最小値を各について求めよ。 解法 愚直にやるなら各クエリに対して…