[AOJ] No. 0411 矢印

2019年12月12日2019年12月17日

問題

方針

空白のマスを〇で表すとします。”→←〇〇” という状態で ”〇→←〇” と矢印を動かしても点数に変化はありません。また、”→→←〇〇” という状態では、”〇→→←〇” と動かすと点数が \( 1 \) 増えます。

最大値を取る矢印の状態は複数ありますが、矢印が左右に分かれている状態の中に最大値を取るものがあります。証明はしていませんが、そうらしいです。

先頭方向に矢印が \( i \) 個固まっているときの点数を \( l_i \) とし、末尾方向のときの点数 \( r_i \) とすると、\( l_i + r_{N – i} \) を全探索すればよいです。\( l, r \) については、累積和を取ることであらかじめ計算しておきます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Data {
    int d;
    ll p;
    Data(ll p, int d) : p(p), d(d){}
    bool operator < (const Data &d) const {
        return p < d.p;
    }
};

int main() {
    int N;
    ll L;
    cin >> N >> L;
    ll p[N];
    int d[N];
    vector<Data> v;
    for (int i = 0; i < N; i++) {
        cin >> p[i] >> d[i];
        v.push_back(Data(p[i], d[i]));
    }
    
    sort(v.begin(), v.end());
    ll l[N + 1]{};
    ll r[N + 1]{};
    for (int i = 0; i < N; i++) {
        if (v[i].d == 0) {
            l[i + 1] = l[i] + v[i].p - i - 1;
        } else {
            l[i + 1] = l[i] - (v[i].p - i - 1);
        }
        if (v[N - i - 1].d == 0) {
            r[i + 1] = r[i] - (L - v[N - i - 1].p - i);
        } else {
            r[i + 1] = r[i] + (L - v[N - i - 1].p - i);
        }
    }
    
    ll ans = 0;
    for (int i = 0; i <= N; i++) {
        ll t = r[i] + l[N - i];
        ans = max(ans, t);
    }
    cout << ans << "\n";
    return 0;
}