けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2010 C - つらら (AOJ 0551, 難易度 6)

実装をどうしようかを色々悩んでしまう系

問題概要

 N 本のつららが一列に並んでいる。それぞれ長さは  A_{1}, \dots, A_{N} となっている。各つららは以下のルールに従って長さが変わる。

  • 一度でも長さが 0 になったならば、伸びることはない
  • 左右のつららの長さが自身よりも短いときに限り、1 秒に 1 cm 伸びる
    • 両端のつららについては、左右のうち片側のつららとのみ比較する
  • 長さが  L になったならば折れて 0 になる

すべてのつららの長さが 0 になるまでの所要時間を求めよ。

制約

  •  2 \le N \le 10^{5}
  •  2 \le L \le 50000

解法 (1):左右から走査

まずサンプルを手を動かして眺めつつ、問題で問われていることをわかりやすく言い換えよう。そうすると、下図のように各つららの長さをプロットしたときに、

  • 「極大つらら」から「極小つらら」へと左方向へ折れが伝播していくパターン
  • 「極小つらら」から「極大つらら」へと左方向へ折れが伝播していくパターン

とがあることがわかる。

f:id:drken1215:20201223110528p:plain

いずれのパターンも試して、すべてのパターンにつての伝播時間の最大値を求めれば OK。

実装上は、

  • dp[i] ← i 番目のつららの長さが 0 になるまでの時間

としておいて、左右両端から走査する感じで実装できる。for 文を「左から右へ」と「右から左へ」を 2 回やる感じ。今回の問題に限らず、こういうジグザグな形をした問題では、左右両方から for 文を回すといいことがあるイメージ。

計算量は  O(N) となる。

コード

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

int main() {
    int N;
    long long L;
    cin >> N >> L;
    vector<long long> a(N+2, 0);
    for (int i = 1; i <= N; ++i) cin >> a[i];

    // 初期条件
    vector<long long> dp(N+2, 0);
    for (int i = 1; i <= N; ++i) {
        if (a[i] > a[i-1] && a[i] > a[i+1]) dp[i] = L - a[i];
    }

    // 左右から DP
    for (int i = 1; i <= N; ++i) {
        if (a[i] < a[i-1]) dp[i] = max(dp[i], dp[i-1] + (L - a[i]));
    }
    for (int i = N; i >= 1; --i) {
        if (a[i] < a[i+1]) dp[i] = max(dp[i], dp[i+1] + (L - a[i]));
    }

    // 答え
    long long res = 0;
    for (int i = 1; i <= N; ++i) res = max(res, dp[i]);
    cout << res << endl;
}

解法 (2):priority_queue を使う

解法 (1) では左右両端から DP した。他にも DP の遷移順序を priority_queue に丸投げしてしまう解法もある。

つまり、つららが大きい順に DP 値が確定していければよいので、つららが大きい順に DP 値が確定していくように、priority_queue を用いるのだ。

計算量は  O(N \log N) となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<long long,int>; // length, index

int main() {
    int N;
    long long L;
    cin >> N >> L;
    vector<long long> a(N+2, 0), dp(N+2, 0);
    priority_queue<pint> que;
    for (int i = 1; i <= N; ++i) cin >> a[i], que.push(pint(a[i], i));

    // DP
    while (!que.empty()) {
        int id = que.top().second;
        que.pop();
        if (a[id] < a[id-1]) dp[id] = max(dp[id], dp[id-1]);
        if (a[id] < a[id+1]) dp[id] = max(dp[id], dp[id+1]);
        dp[id] += L - a[id];
    }

    // 答え
    long long res = 0;
    for (int i = 1; i <= N; ++i) res = max(res, dp[i]);
    cout << res << endl;
}

解法 (3):極大点と極小点を列挙して累積和

解法 (1) と考え方はほぼ同じなのだが、for 文を回すのが 1 回で済む方法。あらかじめ、つららの長さが極小となっている箇所と、極大になっている箇所を列挙する (左右両端も含める)。

そして、各  i について、 i 番目の極大点または極小点を  lとし、 i+1 番目の極大点または極小点を  r としたとき、

 L(r-l+1) - (S_{r+1} - S_{l})

の最大値を求めれば OK。ここで  S A の累積和とした。

コード

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

int main() {
    int N;
    long long L;
    cin >> N >> L;
    vector<long long> a(N), s(N+1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        s[i+1] = s[i] + a[i];
    }
    vector<int> pole({0, N-1});
    for (int i = 1; i < N-1; ++i) {
        if (a[i] > a[i-1] && a[i] > a[i+1]) pole.push_back(i);
        if (a[i] < a[i-1] && a[i] < a[i+1]) pole.push_back(i);
    }
    sort(pole.begin(), pole.end());

    long long res = 0;
    for (int i = 0; i+1 < pole.size(); ++i) {
        int left = pole[i], right = pole[i+1] + 1;
        res = max(res, L * (right - left) - (s[right] - s[left]));
    }
    cout << res << endl;
}