2022-10-01から1ヶ月間の記事一覧

ABC236 E - Average and Median

問題へのリンク Tips. 平均値や中央値の最大化には二分探索が有効 平均値としてあり得る値の最大値 入力例1のとき、次の図のように考えられる。 max_sum は B の隣り合う値の少なくとも一方を選択したときの、選択した値の和とする。 max_sum は簡単なdpを行…

ARC150 B - Make Divisible

問題へのリンク まず、 のときは のときに が最小となる。 以下では のときについて考える。 とする。 このとき式変形すると、 となる。 が固定されているとき、 であるから、 がとりうる最小の となる。 また、 であることから、 を最小化すればよい。 平方…

ABC271 F - XOR on Grid Path

問題へのリンク 解法 まずは全探索を考えたくなる。 マス(1, 1)から(N, N)までの経路を全探索しようとすると、 通りになってしまい、 のときには実行制限時間に間に合わない。 この問題では「半分全列挙」を行うことで高速化することができる。 上図のように…