2019-04-28から1日間の記事一覧
AtCoder
ABC-D
AtCoder500点
累積和
前処理
差分更新
数列
ある量を固定して考える
ある量を決めるとGreedy
priority_queue
K番目を求める
データ構造
累積和テク:左右両端からの累積和や累積結果を前処理
青色diff
ARC-D
中堅以上の典型要素を詰め合わせた教育的問題
制約条件:各グループの何かが等しい
累積和テク:累積和や累積結果を前処理しておく
最大スコア
最適化問題
昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…
AtCoder
AtCoder1200点
AGC-E
二分探索
最大値の最小化
Greedy
最適化テク:最適解の形を考える
最適化テク:解を変形していく(最適性を失わずに)
最適化テク:探索候補を絞る
数列
マッチング
Greedyなマッチング
区間
天才な二分探索
銅色diff
楽しかった。7 時間かかったけど自力 AC できたー! 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…