drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AOJ Greedy Greedyなマッチング N個のものうち1個を変更・削除したものを解く 累積和テク:左右両端からの累積和や累積結果を前処理 累積max 累積和 マッチング 二部マッチング JOI JOI本選 JOI難易度6 各kに対して 数列 最適化の考察：変形しても悪化しない max(pi-pj,0) 累積和テク:累積和や累積結果を前処理しておく ソート:前処理 まずソートして考える Greedy を考察して、さらに左右から累積和を求める！結構難しい！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数列 を考えて、数列 を適切に並び替えたときの、 の値の最小値 制約 考えたこと まずは 通りの値を求める問題をいきなり考えるのではなく、2 つの長さ の数列 があるとして、スコアを最小にするような の並び替え方を考えよう。また、 は小さい順にソートされていると考えて差し支えない。 A もソートしてみる 直… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F11%2F28%2F030300" title="JOI 本選 2020 A - 長いだけのネクタイ (難易度 6) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-11-28 03:03:00 rich https://drken1215.hatenablog.com/entry/2020/11/28/030300 1.0 100%