チェビシェフの不等式
AtCoder
AtCoder400点
ABC-C
茶色diff
数列
操作
最小回数・最小個数を求める
制約条件:和や差が一定値
操作:定数を足したり引いたりする
考察:ソート
操作を好きな回数だけ行える
気付き系
絶対値やminを扱う問題
最適化の考察:最適解の形を考える
チェビシェフの不等式
最適化の考察:変形しても悪化しない
Greedy:交換しても悪化しない
Greedy
均等に分ける
最適化問題
操作:2点を同時に更新
ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…
ランレングス圧縮
AtCoder
AtCoder400点
ABC-D
N個のペア値の問題
Greedy
操作
最適化の考察:変数を入れ替えて考える
考察:一部の変数を固定して考える
操作後の結果の最適化問題
最大スコア
緑色diff
最適化問題
チェビシェフの不等式
NoviSteps2Q
混ぜてソートは賢すぎる!!!惚れた!!! 問題へのリンク 問題概要 枚のカードにそれぞれ の数値が書かれている。あなたは、 について順に以下の操作を 1 回ずつ行います。 カードを 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ …
数列
Greedy
最適化の考察:「≦ K であること」と「= K となる実例」を示す
チェビシェフの不等式
AtCoder
AtCoder400点
各桁ごとに見る
考察:主客転倒・寄与分解
緑色diff
ARC-like
ARC-C
今週のお題「わたしとバレンタインデー」 提出するまでが怖かった 問題へのリンク 問題概要 整数が N 個与えられます。 i 個目の整数は Ai です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。 考えたこと うおっ…