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$が黒く塗られるものは何通りあ…

codeforces.com 問題概要 頂点のグラフ$G$のうち、頂点の次数が数列$a_1,\dots,a_N$として与えられている。$G$が単純無向グラフであるとき、残り1頂点の次数$a_{0}$としてありうるものをすべて答えよ。 制約 $1\leq N\leq 5\times10^5$ $0 \leq a_i \leq N$ …

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

問題 http://codeforces.com/contest/1014/problem/A2 無限に続くマス目の列があり，0,1,2,..と番号がつけられている．それぞれのマスには'A','B',...,'J'の10種類の色のうち1つがつけられている． 与えられた初期状態では，プレイヤーは10色の塗料のボトル…

問題 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)個の組み合わせとなるので，塗り方は 通…

https://yukicoder.me/problems/no/5002yukicoder.me 成績 51,325点 (4位) 最終的な解法 各長方形を{向き(y軸方向 or x軸方向)，左上の点のy座標，左上の点のx座標}の3整数で表した．従って動かせる値は3k個となる． 3k個の整数をランダムに与えることで長方…

codeforces.com 問題 をで求めよ． ( ) editorial解法 とする．ここで が成立している．両辺をで微分してをかけると . 両辺をで微分してをかける操作をさらに回繰り返すと . 右辺でとした値はなので，左辺を評価してとすればを求められる．操作を回行った時…

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