JOI 2018/2019 予選 D - 日本沈没 (Japan Sinks)

JOI 2018/2019 予選 D - 日本沈没 (Japan Sinks) についてのメモを残します。

島の数の推移

• 問題 : JOI 2018/2019 予選 D - 日本沈没 (Japan Sinks)

海水面が上昇していく。このとき、島の数の最大値を求める。

次に沈む区画について、その区画の左右がともに陸 (その区画が左右より低い) ならば、島が 1 つ増える。

また、次に沈む区画について、その区画の左右がともに海 (その区画が左右より高い) ならば、島が 1 つ減る。

実装

実装でハマりました。
結局は、はじめに両端に高さ 0 の区画を加え、同じ高さが連続している部分は圧縮しました。

同じ高さの区画が複数ある場合に注意が必要で、最大値の更新 ans = max(ans, cur); は最後の 1 区画を終えたときにのみ行います。

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

int main() {
  int N; cin >> N;
  vector<int> A(N+2);  // 両端に 0 を追加
  for (int i = 1; i <= N; i++) cin >> A.at(i);
  // 同じ高さが連続する部分は圧縮
  int m = 1;
  for (int i = 1; i < N+2; i++) {
    if (A.at(m-1) != A.at(i)) {
      A.at(m) = A.at(i);
      m++;
    }
  }
  if (m == 1) { cout << 0 << endl; return 0; };  // 高さが全て 0
  vector<pair<int, int>> P;  // first: 高さ, second: index
  // 両端の 0 は無視
  for (int i = 0; i < m-2; i++) {
    P.push_back(make_pair(A.at(i+1), i+1));
  }
  sort(P.begin(), P.end());  // 低いところからシミュレーション
  int ans = 1;  // 初期状態は海面の高さを -1 とする
  int cur = 1;  // 現在の島の数
  for (int i = 0; i < P.size(); i++) {
    int idx = P.at(i).second;
    // となりが両方とも海
    if (A.at(idx-1) < A.at(idx) && A.at(idx) > A.at(idx+1)) cur--;
    // となりが両方とも陸
    if (A.at(idx-1) > A.at(idx) && A.at(idx) < A.at(idx+1)) cur++;
    // 同じ高さが複数あれば、更新は最後の 1 つを終えた後に行う
    if (i+1 == P.size() || P.at(i).first < P.at(i+1).first) {
      ans = max(ans, cur);
    }
  }
  cout << ans << endl;
}