f:id:peroon:20200202090142j:plain

Quiz

https://atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d

AC code

https://atcoder.jp/contests/joi2019yo/submissions/9864231

補足

公式解説 https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t4-review.html
これでなんとなく分かるのだが、実装上の注意ポイントがある
- １：最初から全部沈没している場合（コーナーケース）
- ２：高さが同じものがあるので、それらは同時に沈没させる必要
- ３：高さが同じで連続するものもありうる（例 2 1 1 1 2）
３については意識したくないので、C++のuniqueを使って、連続する同じ数字を除去する（工夫ポイント）

2 1 1 1 2 => 2 1 2

map＜int, vector＜int＞＞で高さごとに添え字を管理して、高さの低いものから沈没させ、島数のmaxを取ってAC

    // 高さごとにリスト管理
    map<ll, VI> mp;
    rep(i, N){
      ll h = H[i];
      mp[h].push_back(i);
    }

Code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin >> N;

    VI H(N);
    rep(i, N) cin>>H[i];

    // 最初から全部沈没は除外
    ll sum = 0;
    for(ll h : H) sum+=h;
    if(sum==0){
      p(0);
      return 0;
    }

    if(N==1 || N==2){
      p(1);
      return 0;
    }

    // 同じ高さの連続は除外
    auto it = unique(ALL(H));
    H.erase(it, H.end());
    N = H.size();

    // 高さごとにリスト管理
    map<ll, VI> mp;
    rep(i, N){
      ll h = H[i];
      mp[h].push_back(i);
    }

    ll island = 1;
    ll ma = 1;
    vector<bool> sink(N);
    for(auto pa : mp){
      // ll h = pa.first;
      VI V = pa.second;
      
      for(auto idx : V){
        sink[idx] = true;
        if(idx==0){
          if(sink[idx+1]) island--;
        }
        else if(idx==N-1){
          if(sink[idx-1]) island--;
        }
        else{
          island++;
          if(sink[idx+1]) island--;
          if(sink[idx-1]) island--;
        }
      }

      chmax(ma, island);
    }
    p(ma);

    return 0;
}