Atcoder Regular Contest 074_D_3N Numbers

Markdownでのテスト投稿.

うまく反映されていると嬉しい.

atcoder.jp

問題の説明

長さの数列があります.ここから個の要素を取り除きを作ります.

スコアをとしたとき,スコアの最大値を求めなさい.

制約

• 
• は整数である.
• 

考えた事

当たり前ではあるが青色の問題なのでかなりタフである.賢いひとはこのレベルであっても一気に解けてしまうのかもしれない.しかし,自分は違う.こういった込み入ったの問題へのアプローチとして有効なのは制約を弱める事だ.

この問題でスコアを求めるとき,「前半」と「後半」に分けるパートが存在する.これを弱めてみよう.つまり,こうするのだ.

「スコアをとしたとき,これの最大値を求めよ.ただし,sortを用いてはならない.」

こうした場合,この問題はどう解くべきだろうか.もちろん最適な解き方は簡単である.から大きい順個を取りだし総和を求め,小さい順個を取り出した総和から引けばいい.

これを実装するにあたってsortを使ってはならないとある.どうしようか.こうあるときにpriority_queueを用いる.

priority_queueにを順に格納し,うち個を出力させれば,大きい順個は把握できるだろう.小さい順も同様だ.今回はこの発想を基本とする.

では制約を元に戻そう.ここで厄介となるのは「前半」と「後半」である.
とあった時に,ここからどう個取り除いたとては「前半」であり,は後半にしか見えないだろう.

これがポイントとなる.つまり,の中には個取り除いてを構築しても,絶対に「前半」になるもの,「後半」となるものが存在する.

何があっても絶対に「前半」となるのはあり,「後半」となるのは[tex:a{2N+1}...a{3N}]である.間はどうか.取り除かれ方によって変わるだろう.

なぜか.「前半」とはの前から見て個のものを指し,「後半」とはの後ろから見て個のものを指すからである.当然,の時点で前から見て個以内にあるものが「後半」に入ってくる事は有り得ないし,逆も然りである.

この間のもの,つまりにおいて「前半」と「後半」を分ける中間点によって,間の[tex:a{N+1}...a{2N}]が「前半」となるか「後半」となるかが変わる.そして中間点が変わればもちろん総和も変わるだろう.

この中間点をどう調べようか.全探索である.中間点の候補はまでなのだから1つ1つ自分で置き,「前半」と「後半」を分けるのだ.「前半」からN個選んだ中での合計の最大値,「後半」からN個選んだ場合の合計の最小値はpriority_queueを用いて計算できる.

実装に関する話をしよう.これを実装するにあたって,
中間点毎に全部priority_queueへ押し込む→個になるまでpop→中間点が変わったから全部priority_queueに押し込む→......
とするのはあまりにも無駄が多い.時間量でいっても中間点の候補が個,priority_queueに回押し込む,個まで削除を繰り返すと,計算量はとなり,制約から明らかにTLEが見えてしまう.

ここで使いたいのは累積和の発想だ.まず予めの前から個を priority_queueに押し込み,その総和も求めておく.

その後中間点が変わる毎に priority_queueへデータを追加し,総和も増やしておく.それから1つpopして,総和からも引く.
これを繰り返す事で中間点が変わってもの「前半」部分の最大値を求められる.これは計算量がとなり,間に合う.

最小値に関しても同様に行えばよい.イメージは以下の通り.

rep(i, N) {
        max += a.at(N + i);
        mque.push(a.at(N + i));
        max -= mque.top();
        mque.pop();
        maxi.push_back(max);
    }

以上をからまで行い,その中での(最大値)-(最小値)のうちから最大値を出力すれば答えとなる.お読みいただきありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<long long>;
const long long INF = 1e18;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define ALL(n) begin(n), end(n)
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}

int main() {
    ll N;
    cin >> N;
    vll a(3 * N);
    rep(i, 3 * N) { cin >> a.at(i); }
    priority_queue<ll> Mque;
    priority_queue<ll, vll, greater<ll>> mque;
    ll max = 0;
    ll min = 0;
    vll maxi;
    vll mini;
    rep(i, N) {
        mque.push(a.at(i));
        max += a.at(i);
    }
    maxi.push_back(max);
    rep(i, N) {
        max += a.at(N + i);
        mque.push(a.at(N + i));
        max -= mque.top();
        mque.pop();
        maxi.push_back(max);
    }
    reverse(ALL(a));
    rep(i, N) {
        Mque.push(a.at(i));
        min += a.at(i);
    }
    mini.push_back(min);
    rep(i, N) {
        min += a.at(N + i);
        Mque.push(a.at(N + i));
        min -= Mque.top();
        Mque.pop();
        mini.push_back(min);
    }
    reverse(ALL(mini));
    ll sum = -INF;
    rep(i, N + 1) { CHMAX(sum, maxi.at(i) - mini.at(i)); }
    cout << sum << endl;
}