7K12B blog

猫でも分かる何か

2021-03-01から1ヶ月間の記事一覧

ABC173 E - Multiplication 4

https://atcoder.jp/contests/abc173/submissions/21143239 K個選んだときの積が負なら「負を1つ減らして正を1つ増やす」「正を1つ減らして負を1つ増やす」両方を試す必要がある 積を最大化するため、絶対値降順に貪欲にK個だけ選ぶ(実際に計算するとオーバ…

ARC043 B - 難易度

https://atcoder.jp/contests/arc043/submissions/20924727 初期値は dp[0][0] = ... = dp[0][N-3] = 1 繰り返しは each(i, e, D) rep(j, 1, 4) 漸化式は dp[j].Add(i, dp[j - 1].Sum(0, distance(D.begin(), upper_bound(all(D), e / 2)))) 最終目標は Sum(…

ABC036 D - 塗り絵

https://atcoder.jp/contests/abc036/submissions/20748614 初期値はall(dp) = 1; 繰り返しは DFS 漸化式は dp[now][B] *= dp[next][W], dp[now][W] *= dp[next][B] + dp[next][W]; 最終目標は dp[0][B] + dp[0][W]; 葉からDPを更新することで根が答えになる…

AGC006 B - Median Pyramid Easy

https://atcoder.jp/contests/agc006/submissions/20609588 中央値なので小中大(x-1, x, x+1)で並べる x, x, y の中央値は x まず、一番上の段がxになるようにしないといけないので真ん中にxを置きたくなる(ぇ 次に、中央値なので x-1, x, x+1 と数字を並…