けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

最適化テク:自明な上界が最適解

AtCoder ABC 103 C - Modulo Summation (茶色, 300 点)

が互いに素でない場合とか一瞬だけ怖くなるけど、信じて提出する!!!!!!! 問題へのリンク 問題概要 個の整数 が与えられる。 様々な非負整数 に対して を で割ったあまり を で割ったあまり を で割ったあまり の総和を考えたとき、その最大値を求めよ…

AtCoder ABC 101 C - Minimization (ARC 099 C) (緑色, 300 点)

ARC 099 C - Minimization 問題概要 1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。 連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える 制約 1 <= K <= N <= 105 解法 間違いや…