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

問題概要

$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)：左右から走査

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

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

とがあることがわかる。

いずれのパターンも試して、すべてのパターンにつての伝播時間の最大値を求めれば 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;
}

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

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

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

問題概要

制約

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

コード

解法 (2)：priority_queue を使う

コード

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

コード