Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

C2. Pokémon Army (hard version) (Codeforces Round #672 Div. 2)

問題

https://codeforces.com/contest/1420/problem/C2

問題概要

長さnの配列aが与えられる。この配列の部分列を、その要素を左から順に加算減算加算減算・・・したときの演算結果が最大になるように取りたい。最大値はいくつになるか。(ここまでC1)

また整数qが与えられる。配列aの2つの要素がq回swapされるので、swapされたあとの最大値を都度答えよ。(C1の分とあわせてq+1回答えることになる)

考察

C1

これは配列aの値の極大を加算、極小を減算していけばよいです。

考え方としては(結構違うけど)D - Road to Millionaireと雰囲気が似ているでしょうか。

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP1(i, n) FOR(i, 1, (n) + 1)
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<ll> a(n + 2);
        a[0] = 0;
        a[n + 1] = 0;
        REP1(i, n) cin >> a[i];
        ll ans = 0;
        REP1(i, n) {
            if (a[i - 1] < a[i] and a[i] > a[i + 1]) ans += a[i];
            else if (a[i - 1] > a[i] and a[i] < a[i + 1]) ans -= a[i];
        }
        cout << ans << endl;
    }
 
    return 0;
}

C2

つよつよな競プロerの人たちはすぐにセグ木を持ち出したらしいですが、特にそのようなデータ構造を持ち出さずともO(q)で解く方法があります。

lとrをswapしたとき、影響を受けるのはそれぞれの前後±1だけなので、その部分だけ一旦リセットしてから再計算をすればよいです。一旦リセットするために、極大と極小の出現位置は記録しておく必要があります。

また、lとrが接近しているときに再計算部分がかぶってしまうことに気をつけることと、l=0r=n-1のとき範囲外アクセスをしてしまわないように気をつける必要があります。

(2020-09-26 01:02追記) 以下のコード、TLEするっぽいです・・・。後で直します。

(2020-09-26 13:09追記) 結局何が悪いのかわかりませんでした。(え

なお本番で通したときのコードがこちらです。(コピペがひどい) https://codeforces.com/contest/1420/submission/93694592

これをきれいにまとめただけのつもりなんですが・・・。

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, (n))
#define REP1(i, n) FOR(i, 1, (n) + 1)
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<ll> a(n + 2);
        a[0] = 0;
        a[n + 1] = 0;
        REP1(i, n) cin >> a[i];
        vector<pair<int, int>> b(q);
        REP(i, q) cin >> b[i].first >> b[i].second;
        vector<int> x(n + 2);
        ll ans = 0;

        auto calc = [&](int d) {
            if (a[d] == 0) return;
            x[d] = 0;
            if (a[d - 1] < a[d] and a[d] > a[d + 1]) {
                ans += a[d];
                // 極大位置を覚える
                x[d] = 1;
            } else if (a[d - 1] > a[d] and a[d] < a[d + 1]) {
                ans -= a[d];
                // 極小位置を覚える
                x[d] = -1;
            }
        };
        
        REP1(i, n) calc(i);
        cout << ans << endl;

        auto reset = [&](int d) {
            if (x[d] > 0) ans -= a[d]; else if (x[d] < 0) ans += a[d];
        };

        int l, r;
        REP(i, q) {
            tie(l, r) = b[i];
            if (l + 1 == r) {
                FOR(j, l - 1, r + 2) reset(j);
                swap(a[l], a[r]);
                FOR(j, l - 1, r + 2) calc(j);
            } else if (l + 2 == r) {
                FOR(j, l - 1, r + 2) reset(j);
                swap(a[l], a[r]);
                FOR(j, l - 1, r + 2) calc(j);
            } else {
                FOR(j, l - 1, l + 2) reset(j);
                FOR(j, r - 1, r + 2) reset(j);
                swap(a[l], a[r]);
                FOR(j, l - 1, l + 2) calc(j);
                FOR(j, r - 1, r + 2) calc(j);
            }
            cout << ans << endl;
        }
    }

    return 0;
}